题目描述

给定一个编码字符串 S。为了找出 解码 字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

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

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

样例

输入：S = "leet2code3", K = 10
输出："o"
解释：
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。

输入：S = "ha22", K = 5
输出："h"
解释：
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。

输入：S = "a2345678999999999999999", K = 1
输出："a"
解释：
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。

注意

• 2 <= S.length <= 100
• S 只包含小写字母与数字 2 到 9 。
• S 以字母开头。
• 1 <= K <= 10^9
• 解码后的字符串保证少于 2^63 个字母。

算法

(回溯) $O(n)$

1. 首先计算出解码后的字符串的长度 len。
2. 然后倒序遍历字符：(1) 当前字符为小写字母，若 K == len，则说明当前字母就是索引 K，直接返回；否则 len 自减 1。(2) 当前字符为数字，则先将 len = len / S[i]，找到重复之前的长度。若 K % len == 0，则说明索引 K 是循环节的最后一个字母，则直接从 i 开始向前找到第一个字母并返回即可。否则，K = K % len。

时间复杂度

• 计算长度的只需要遍历一遍，倒序找答案也最多只需要遍历一次，故总时间复杂为 $O(n)$。

空间复杂度

• 仅使用的常数的额外空间，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    #define LL long long
    string decodeAtIndex(string S, int K) {
        int n = S.length();
        LL len = 0;
        for (auto &c : S) {
            if (isalpha(c))
                len++;
            else
                len *= c - '0';
        }

        for (int i = n - 1; i >= 0; i--) {
            if (isalpha(S[i])) {
                if (K == len)
                    return S.substr(i, 1);
                len--;
            }
            else {
                len /= S[i] - '0';
                if (K % len == 0) {
                    for (int j = i - 1; j >= 0; j--)
                        if (isalpha(S[j]))
                            return S.substr(j, 1);
                }
                K %= len;
            }
        }

        return "";
    }
};