难度: Medium
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 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] 运行时间: 18 ms
内存: 16.0 MB
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = '', 0
elif c == ']':
cur_multi, last_res = stack.pop()
res = last_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c) # 可能不是个位数
else:
res += c
return res
这个题解使用了一个栈来保存括号外面的状态。当遇到'['时，将当前的multi和res压入栈中，然后重置它们。当遇到']'时，从栈中弹出上一层的multi和res，并将当前的res乘以multi次，然后与上一层的res相连。如果遇到数字，则更新multi的值。如果遇到字母，则将其添加到当前的res中。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], '', 0
for c in s:
if c == '[':
stack.append([multi, res]) # 将当前multi和res压入栈
res, multi = '', 0 # 重置res和multi
elif c == ']':
cur_multi, last_res = stack.pop() # 弹出上一层的multi和res
res = last_res + cur_multi * res # 构建新的res
elif '0' <= c <= '9':
multi = multi * 10 + int(c) # 更新multi
else:
res += c # 添加字母到res
return res
当遇到嵌套括号时，算法通过使用栈来保存每一层的状态，确保每一层的解码可以独立进行。例如，对于输入'3[a2[c]]'，当遇到第一个'['时，将当前multi（3）和res（空字符串）压入栈。接着，遇到第二个'['时，已经更新了res为'a'和multi为2，所以再次将这些压入栈。当遇到第一个']'时，解码内层括号'2[c]'，结果为'cc'，并将其与之前栈中保存的res（'a'）相加，得到'acc'。再遇到外层的']'时，将'acc'重复3次，得到最终结果。这种使用栈的方式可以自然地处理嵌套结构，并确保每一层的解码正确完成。
这种方式用于处理多位数字，因为输入中的数字可能不只是一位数，例如'12[a]'。通过这种方式，我们可以将连续的数字字符组合成完整的整数。这种方法在正常情况下不会遇到问题，但如果数字非常大，可能会导致整数溢出。在Python中，整数类型可以自动处理大数，但在其他编程语言中可能需要额外注意整数溢出的问题。
这种方法可以正确处理连续的字母。每遇到一个字母字符，就将其追加到当前的res字符串中。这种处理方式在大多数情况下效率是可以接受的，但如果输入字符串非常大，频繁的字符串连接可能会导致性能问题，因为每次添加字符都可能涉及创建新的字符串和复制旧内容。在一些性能敏感的场景下，可以考虑使用更高效的数据结构，如字符串构建器（StringBuilder或StringBuffer），来优化连续字符的处理。
栈是后进先出（LIFO）的数据结构，这在处理嵌套结构时非常有用。每当遇到'['时，就将当前的multi和res压入栈，这保证了每进入一个新的括号层级，外层的状态都被保存了。当遇到']'时，从栈中弹出元素，这保证了弹出的状态是对应当前闭合括号最近的未闭合括号的状态。这样，每次处理闭合括号时，都可以得到正确的外层状态，并据此构建当前层的结果。这种方式自然地处理了嵌套，并确保了数据的正确性与操作的顺序性。