394. Decode String

[fockspaces]

類似處理四則運算

1. 做 stack 紀錄 chars, digits
2. 遇到 '['，收集 digits，並讓 chars 多進一位，表示 decode level
3. 遇到 ']'，把當前 stack top 的 digits, chars 抓出來 decode，再將 decode_string 擺回上一層 level chars
4. 遇到數字，計算 cur_num
5. 遇到字母即放入 chars 紀錄

class Solution:
    def decodeString(self, s: str) -> str:
        chars, nums, cur_num = [], [], 0
        s = '1[' + s + ']'
        for c in s:
            if c.isdigit():
                cur_num = cur_num * 10 + int(c)
            elif c == '[':
                nums.append(cur_num)
                chars.append("")
                cur_num = 0
            elif c == ']':
                # start decode
                encode_str, counts = chars[-1], nums[-1]
                chars.pop()
                nums.pop()
                decode_str = encode_str * counts
                if chars:
                    chars[-1] += decode_str
                else:
                    chars.append(decode_str)
            else:
                chars[-1] += c
        return "".join(chars)

[fockspaces]

這邊要注意

1. input string 有可能是最外圍沒包裝，如 "asf4[abc]j"，可以手動將其包成 1[asf4[abc]j] 變為 general case 統一處理
2. 100[abc] 會被視作 1, 0, 0，要用 cur_num 紀錄，再由 '[' 判斷何時收集

[fockspaces]

GPT improve:

1. stack 可以存 tuple (string, num）資訊
2. chars 進位邏輯可以直接改用 cur_string 來做簡化，也直接省去最外層包裝
3. cur_string 為所求，會隨著 decode append 進去
4. 遇到 '[' 代表當前 cur_string, cur_num 不是要 decode 的對象，先放 stack 擺一邊
5. 遇到 ']' 即開始處理 cur，並將結果加到 cur_string

class Solution:
    def decodeString(self, s: str) -> str:
        stack, cur_num, cur_string = [], 0, ""
        for c in s:
            if c.isdigit():
                cur_num = cur_num * 10 + int(c)
            elif c == '[':
                stack.append((cur_string, cur_num))
                cur_string, cur_num = "", 0
            elif c == ']':
                last_string, counts = stack.pop()
                cur_string = last_string + cur_string * counts
            else:
                cur_string += c
        return cur_string