题目

给定一个编码字符串 S。请你找出 解码字符串 并将其写入磁带。

解码时，从编码字符串中 每次读取一个字符 ，并采取以下步骤：

如果所读的字符是字母，则将该字母写在磁带上。

如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。

现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

示例 1：输入：S = "leet2code3", K = 10 输出："o"

解释：解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。

字符串中的第 10 个字母是 "o"。

示例 2：输入：S = "ha22", K = 5 输出："h"

解释： 解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。

示例 3：输入：S = "a2345678999999999999999", K = 1 输出："a"

解释： 解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。

提示：2 <= S.length <= 100

S 只包含小写字母与数字 2 到 9 。

S 以字母开头。

1 <= K <= 10^9

题目保证 K 小于或等于解码字符串的长度。

解码后的字符串保证少于 2^63 个字母。

解题思路分析

1、遍历；时间复杂度O(n)，空间复杂度O(1)

func decodeAtIndex(S string, K int) string {
   count := 0 // 字符个数
   n := len(S)
   for i := 0; i < n; i++ { // 先统计最终字符串总长数
      if '0' <= S[i] && S[i] <= '9' {
         value := int(S[i] - '0')
         count = count * value // 重写d-1次，长度是原来的d倍
      } else {
         count++ // 非数字，长度+1
      }
   }
   for i := n - 1; i >= 0; i-- {
      K = K % count                             // 缩小范围
      if K == 0 && 'a' <= S[i] && S[i] <= 'z' { // 找到目标字符
         return string(S[i])
      }
      if '0' <= S[i] && S[i] <= '9' { // 范围缩小
         value := int(S[i] - '0')
         count = count / value
      } else {
         count-- // 长度-1
      }
   }
   return ""
}

2、递归；时间复杂度O(n)，空间复杂度O(1)

func decodeAtIndex(S string, K int) string {
   count := 0 // 字符个数
   n := len(S)
   for i := 0; i < n; i++ { // 先统计最终字符串总长数
      if '0' <= S[i] && S[i] <= '9' {
         value := int(S[i] - '0')
         prev := count
         count = count * value // 重写d-1次，长度是原来的d倍
         if count >= K {
            return decodeAtIndex(S[:i], (K-1)%prev+1) // 缩小范围：避免求余出现0的情况
         }
      } else {
         count++ // 非数字，长度+1
         if count == K {
            return string(S[i])
         }
      }
   }
   return ""
}

总结

Medium题目，注意理解题目，通过缩小范围来找到目标字符