880. 索引处的解码字符串

Difficulty
Medium
Tags
字符串
栈
URL
https://leetcode-cn.com/problems/decoded-string-at-index/comments/
Star
❤
给定一个编码字符串 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 暴力模拟

思路
完整的保存解码字符串，直到当前解码字符串长度达到k
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        res = 0
        cur_idx = 0
        decode_str = []
        while len(decode_str) < k:
            cur_char = s[cur_idx]
						# 如果是字母，直接加入
            if cur_char.isalpha():
                decode_str.append(cur_char)
                cur_idx += 1
		        # 如果是数字，复制解码字符串
            elif cur_char.isdigit():
                cur_idx += 1
                decode_str *= int(cur_char)
                
        return decode_str[k-1]

法 2 栈

遇到数字 d 时，可以不保存重复部分，重复部分的信息可以向前查到。
用栈保存解码字符串每一步的 size 和对应字母即可。比如示例 2：
ha		[(1, h), (2, a)]	
ha2		[(1, h), (2, a), (4, a)]
ha22		[(1, h), (2, a), (4, a), (8, a)]
这样得到的栈便已经包含了所有位置信息。比如查询第 7 位等价于查第 7 % 4 = 3 位，等于查第 3 % 2 = 1 位为 h。注意特殊情况 K % size == 0 时等价于第 size 位，所以终止条件是 K % size == 0。
class Solution:
    def decodeAtIndex(self, S, K):
        stack, size = [], 0
        for char in S:
            if char.isalpha():
                size += 1
                stack.append((size, char))
            elif char.isdigit():
                size *= int(char)
                stack.append((size, stack[-1][1]))

        while K % stack[-1][0]:
            K %= stack.pop()[0]

        return stack[-1][1]