394. 字符串解码 - 力扣LeetCode给定一个经过编码的字符串返回它解码后的字符串。编码规则为:k[encoded_string]表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数k例如不会出现像3a或2[4]的输入。测试用例保证输出的长度不会超过105。示例 1输入s 3[a]2[bc]输出aaabcbc示例 2输入s 3[a2[c]]输出accaccacc示例 3输入s 2[abc]3[cd]ef输出abcabccdcdcdef示例 4输入s abc3[cd]xyz输出abccdcdcdxyz提示1 s.length 30s由小写英文字母、数字和方括号[]组成s保证是一个有效的输入。s中所有整数的取值范围为[1, 300]显然使用栈更方便抓住[和]必须成对出现第一步遍历 s只要不是]就直接入栈第二步一旦遇到]说明当前已经具备了解码的条件要找到与这个右中括号匹配的左中括号即最近的那个左中括号。因此往回找并把往回找的过程中遍历到的字符放入一个临时字符串 sub 当中因为后续我们要把这些字符压入栈中。即往回找的过程中如果遇到的不是[那么就 pop 并放入到 sub 当中如果是直接 pop 不需要放入 sub走完这一步已经把两个匹配的中括号里面的字符串提取出来了第三步把这对中括号的前缀数字提取出来才知道要循环几遍。由于在 s 中的是字符而非数字所以要求出数字的值。比如46[abc]你不能只提取出来 4 和 64 和 6 应当是一个整体46. 因此我们同样往回遍历循环的条件是栈不为空因为数字可能放在最开头且栈的最后一位是数字用 k 记录这个数字的最终的值base 记录进位一开始 k 为 0 base 为 1每遍历到一个数字k 就加上这个数字乘 base 的值然后 base 再自乘 10 . 循环结束之后这个数字的值就是 k 的值第四步把 k 个 sub 压入栈中即便有嵌套也是没问题的因为我们是先从最里面的那一对解码的class Solution: def decodeString(self, s: str) - str: stk [] for ch in s : # 第一步不是 ] 就入栈 if ch ! ] : stk.append(ch) continue # 第二步解码往回找 [ , 并把字符放入 sub 中 sub while stk[-1] ! [ : sub stk.pop() sub # pop 出的元素应该放在 sub 前面 stk.pop() # 移出 [ # 第三步提取数字 k, base 0, 1 while stk and stk[-1].isdigit() : k int(stk.pop()) * base base * 10 # 第四步把 k 个 sub 压入栈中 stk.append(k * sub) return .join(stk)