索引处的解码字符串

难度: Medium

给定一个编码字符串 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 个字母。

Submission

运行时间: 29 ms

内存: 16.1 MB

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        lst, n = [""], 0
        for c in s:
            if c.isalpha():
                if type(lst[-1]) == str: lst[-1] += c
                else: lst.append(c)
                n += 1
            else:
                lst.append(x := int(c))
                n *= x
                if n >= k: break
        for v in lst[::-1]:
            if type(v) == int: 
                n //= v
                k %= n
            else:
                if k == 0: return v[-1]
                if n - k < (x := len(v)): return v[::-1][n - k]
                n -= x

Explain

该题解的思路是记录编码字符串每个字符解码后对应的字符串长度。对于字母字符，将其追加到结果列表的最后一个字符串元素中；对于数字字符，将其转换为整数，追加到结果列表中，并用其乘以当前字符串长度。这样可以快速定位解码后第K个字符所在的位置。最后，从后向前遍历结果列表，如果遇到整数，则将当前字符串长度整除该整数，并对K取模；如果遇到字符串，则判断第K个字符是否在该字符串内，如果在则直接返回对应字符。

时间复杂度: O(N)

空间复杂度: O(N)

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        lst, n = [""], 0  # 初始化结果列表和当前字符串长度
        for c in s:
            if c.isalpha():
                if type(lst[-1]) == str: lst[-1] += c  # 如果最后一个元素是字符串，将当前字母追加到该字符串
                else: lst.append(c)  # 否则，将当前字母作为新的字符串元素追加到结果列表
                n += 1  # 当前字符串长度加1
            else:
                lst.append(x := int(c))  # 将当前数字字符转换为整数，追加到结果列表
                n *= x  # 当前字符串长度乘以该整数
                if n >= k: break  # 如果当前字符串长度大于等于K，则停止遍历
        for v in lst[::-1]:  # 从后向前遍历结果列表
            if type(v) == int:  
                n //= v  # 如果当前元素是整数，将当前字符串长度整除该整数
                k %= n  # 对K取模
            else:
                if k == 0: return v[-1]  # 如果K为0，则返回当前字符串的最后一个字符
                if n - k < (x := len(v)): return v[::-1][n - k]  # 如果第K个字符在当前字符串内，则返回对应字符
                n -= x  # 否则，将当前字符串长度减去当前字符串的长度

Explore

在解码字符串的过程中，数字字符表示其前面的字符串应该重复的次数。例如，如果有字符串 'abc' 后跟数字 3，则解码结果应该是 'abcabcabc'。因此，数字字符后的整个字符串长度实际上是当前累积的字符串长度乘以该数字。这种方法通过简单的乘法操作来模拟字符串的重复过程，避免了实际创建重复的字符串，从而节省了空间和时间。这个逻辑通过将字符串长度视为一种可以通过数学运算扩展的 '虚拟长度'来确保正确性，而不是物理上的字符串长度。

反向遍历的目的是从解码字符串的末端开始逐层解构，直到找到第 K 个字符。遇到整数时，意味着之前的字符串发生了重复，此时通过将当前字符串长度整除该整数，减少解码字符串的长度，反映出在未重复之前的长度。同时，对 K 取模是为了找到在未重复前字符串中的相对位置。遇到字符串时，先判断 K 是否为 0，若为 0 则直接返回字符串最后一个字符，因为这表示 K 正好指向该字符串的末尾。如果不是，则检查 K 是否小于当前字符串的长度，如果是，则直接在当前字符串中找到相应的字符。这个过程不断重复，直到找到第 K 个字符。

题解中提到，如果`n >= k`就停止遍历的目的是为了效率。因为一旦当前的虚拟字符串长度 n 超过了 K，表示在这个长度内已经包含了目标位置的字符，因此无需继续处理后续的输入。这种方法实际上并不会构建完整的解码字符串，而是仅仅确定足够的长度以找到第 K 个字符，从而避免不必要的计算和存储。这种策略是有效的，因为题目只要求找到特定位置的字符而不是输出完整的解码字符串。

在解码过程中，通过对 K 进行取模操作，K 可能会减少到 0，特别是当 K 正好等于当前处理字符串的长度的倍数时。例如，若当前字符串长度为 5，且 K 更新后为 10，那么 K % 5 等于 0。此时，K 为 0 表示我们需要的字符正好是这个字符串的最后一个字符。因此，返回 `v[-1]` 是因为在字符串被重复展开后，最后一个字符是重复部分的末尾字符，这符合取模后 K 为 0 的情况。