Decode String
编码字符串会用 k[text] 表示重复的文本：将 text 连续写 k 次。分组可以嵌套，所以 2[a3[b]] 表示 abbbabbb。给定编码字符串 s，返回解码后的字符串。
所有方括号外的字母都保持不变。每个计数都是紧挨着 [ 前面的正整数，数字不会出现在其他位置。
函数
- sstring
- 编码后的字符串
- 返回值string
- 解码后的字符串
约束条件
1 ≤ s.length ≤ 104s只包含小写英文字母、数字、[和]。s是一种有效的编码：每个[前面都有一个计数，并且都有对应的]，没有空括号。- 每个计数
k都满足1 ≤ k ≤ 300，且没有前导零。 - 括号最多可嵌套 100 层。
- 解码后的字符串最多有
5 × 104个字符。
示例
- 输入
- s = "2[ab]3[c]x"
- 输出
- "ababcccx"
- 解释
2[ab]得到abab，3[c]得到ccc。x位于所有方括号之外，会原样复制：ababcccx。
- 输入
- s = "2[x3[yz]]"
- 输出
- "xyzyzyzxyzyzyz"
- 解释
- 先解码内部：
3[yz]是yzyzyz，所以外层内容是xyzyzyz。写两遍就是xyzyzyzxyzyzyz。
- 输入
- s = "q10[w]e"
- 输出
- "qwwwwwwwwwwe"
- 解释
- 这个计数是
10，由两位数字组成，所以w在q和e之间出现十次。
进阶
解码后的字符串可能远长于输入。当它的长度可能达到 10^18 时，怎样才能不构造整个字符串就返回位置 i 处的字符？
提示
逐个打开提示，每个都会多透露一点。
在你知道方括号里是什么之前，不能写出
3[...]，而方括号里还可以包含更多组。哪种组可以让你随时直接解码？不包含其他组的组可以立即展开，因此要从内向外处理。当遇到
]时，它所关闭的组就完成了，你需要取出在它的[之前等待的文本和计数。扫描一次，同时保留目前构建的文本和正在读取的数字。遇到
[时，将两者都压入栈中，然后重新开始。遇到]时，将它们弹出，并把当前文本重复相应次数后，追加到弹出的文本后面。逐位构建每个计数，这样10和300就能正常处理。
题解
在知道一个组的内容之前，你无法写出这个组的副本，而组的内容还可以包含更多组。因此，每种方法都会先完成最内层的组：从内到外重写字符串，递归处理每个组的内容，或者把尚未完成的外层组保存在栈中。这里，n 是输入长度，m 是解码后的长度，d 是嵌套深度。
展开最内层的组，然后重复
思路
找到一个内部没有其他组的组，在原位置写出它的重复内容，然后继续查找。第一个 ] 总是闭合这样的组：在它之前没有组被闭合，所以它的主体中不含括号。它左边最近的 [ 与它匹配，前面的那串数字就是重复次数。在 2[x3[yz]] 中，先展开 3[yz]，得到 2[xyzyzyz]，再展开一次就能得到答案。
每次展开都会重新构建整个字符串。若有 b 个组，输出包含 m 个字符，就最多需要复制 b × m 次：1,000 个组解码后得到 50,000 个字符，最多需要复制 5 × 10^7 次。
算法
- 找到第一个
]。如果没有，就返回字符串。 - 向左找到最近的
[。它们之间的文本就是正文。 - 读取
[前面的数字，将其作为计数k。 - 将从第一个数字到
]之间的所有内容替换为重复k次的正文，然后重复此过程。
def decodeString(s):
# Expand one innermost group at a time until no bracket is left.
while True:
close = s.find("]")
if close == -1:
return s
# The first ']' closes a group with no group inside it,
# and the nearest '[' to its left opens that group.
open_ = s.rfind("[", 0, close)
start = open_
while start > 0 and s[start - 1].isdigit():
start -= 1
times = int(s[start:open_])
s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]递归下降
思路
编码字符串由字母和组构成，组的内容本身也是编码字符串。因此，一个函数 decode 会从共享位置开始读取，直到遇到 ] 或输入末尾，并为每组的内容调用自身。这个调用会在遇到匹配的 ] 时停止，因为每个更深层的 ] 都已由更深层的调用处理。对于 2[x3[yz]]，最内层的调用会返回 yz，中间层的调用会返回 xyzyzyz，外层调用则会将它写入两次。
每个输入字符只读取一次，但每个输出字符会根据它周围的组被复制相应次数：时间复杂度为 O(n + m·d)。递归深度为 d 次调用。
算法
- 保留一个位置
pos，供每次调用共享，并从 0 开始。 decode()会在pos仍位于字符串内且不指向]时循环。- 遇到字母时，将它追加进去并继续前进。
- 遇到数字时，读取整个数字
k，跳过[，调用decode()处理主体，跳过]，然后将主体追加k次。 - 返回构建的内容。第一次调用会返回解码后的字符串。
def decodeString(s):
pos = 0
def decode():
# Read from pos up to the ']' that closes this level, or the end.
nonlocal pos
parts = []
while pos < len(s) and s[pos] != "]":
if s[pos].isdigit():
times = 0
while s[pos].isdigit():
times = times * 10 + int(s[pos])
pos += 1
pos += 1 # skip '['
inner = decode() # the group's body, fully decoded
pos += 1 # skip ']'
parts.append(inner * times)
else:
parts.append(s[pos])
pos += 1
return "".join(parts)
return decode()用栈进行一次遍历
思路
递归会在调用帧中为每个尚未闭合的组保留一段未完成的文本。你可以把这些片段放到自己的栈上，这样解码就只需要一个循环。[ 会将当前层目前解码出的文本及其计数保存起来，并从空文本开始处理组内内容。] 会弹出这些内容，并将重复的副本追加到保存的文本后面。组的闭合顺序与打开顺序相反，因此栈顶始终是 ] 要返回的那一层。
在 2[x3[yz]] 中，你先压入（空文本，2），然后压入（x，3）。第一个 ] 弹出（x，3），此时 current 变为 xyzyzyz；最后一个弹出（空文本，2），并将它重复两次。工作量与递归相同，为 O(n + m·d)，但嵌套很深时增长的是列表，而不是调用栈。
算法
- 从一个空栈、一个空的
current和count = 0开始。 - 遇到数字时，设置
count = count × 10 + digit。 - 遇到
[时，压入（current，count），然后将两者重置。 - 遇到字母时，将它追加到
current。 - 遇到
]时，弹出（before，k），并将current设置为before后接current的k个副本。 - 返回
current。
def decodeString(s):
stack = [] # one entry per open '[': (the text before it, its count)
current = [] # pieces of the text at the current level
count = 0
for ch in s:
if ch.isdigit():
count = count * 10 + int(ch) # counts can have several digits
elif ch == "[":
stack.append((current, count))
current, count = [], 0
elif ch == "]":
before, times = stack.pop()
before.append("".join(current) * times)
current = before
else:
current.append(ch)
return "".join(current)
易错点和边界情况
- 把一位数字当作整个计数。在
q10[w]e中，计数是 10；如果只读取[前面的数字，就会将w重复 0 次。 - 推入
count后没有将它重置为 0。这样，下一组数字就会接在旧数字后面，所以2[a3[b]]会把内部计数读作 23。 - 把重复内容放在已保存的文本前面。
ab2[c]是abcc，不是ccab。 - 漏掉顶层字母。
2[ab]3[c]x中的x也应放入答案。 - 每次只向不可变字符串追加一个字符。每次追加都可能复制整个字符串，因此生成一个 50,000 个字符的答案需要复制超过 10 亿个字符。请将片段收集到列表或字符串构建器中。
常见问题3
Decode String 的时间复杂度是多少？
读取输入的时间复杂度是 O(n)。每个输出字符都会在其周围的每一组中被复制一次，因此总复杂度是 O(n + m·d)，其中 m 是解码后的长度，d 是嵌套深度。当每个计数都至少为 2 时，复制次数不会超过 2m。没有任何方法能优于 O(m)，因为答案有 m 个字符。
你应该用递归还是栈来解决 Decode String？
两者完成的工作相同。递归直接遵循这种格式，因为组的主体本身就是一个编码后的字符串，而且通常是最快的写法。栈版本在一个循环中运行，并将尚未完成的层级保存在列表中，因此，即使输入嵌套了数千层，也不会导致调用栈溢出。
如何处理超过一位数的计数？
边读取数字边构造它：从 0 开始，每读到一位数字，就设置 count = count × 10 + digit。遇到 [ 时，数字就构造完成了，因此 300[a] 表示 300。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def decodeString(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "2[ab]3[c]x"
预期输出
"ababcccx"