leetcode394

leetcode394题是"字符串解码"（Decode String）。

题目描述：
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
可以保证输入字符串总是有效的，没有额外的空格，且输入的方括号格式始终正确。

示例：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

解释：
"3[a]2[bc]" 解码后为 "aaabcbc"。

解题思路：
我们可以使用栈来解决这个问题。遍历输入字符串 s 的每个字符 c：
1. 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
2. 当 c 为字母时，在 res 尾部添加 c；
3. 当 c 为左括号时，将当前 multi 和 res 入栈，并分别置空置 0：
- 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
- 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串。
进入到新 [ 后，multi 和 res 重新记录。
4. 当 c 为右括号时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，
last_res 是上个 [ 到当前 [ 的字符串，cur_multi 是当前 [ 到 ] 内字符串的重复倍数。
5. 遍历结束后返回结果 res。

代码实现如下：

def decodeString(s: str) -> str:
    stack = []
    res = ""
    multi = 0
    for c in s:
        if '0' <= c <= '9':
            multi = multi * 10 + int(c)
        elif c == '[':
            stack.append((multi, res))
            multi = 0
            res = ""
        elif c == ']':
            cur_multi, last_res = stack.pop()
            res = last_res + cur_multi * res
        else:
            res += c
    return res