Leetcode # 394. Decode String

https://leetcode.com/problems/decode-string/

Solution: Stack

遇到 “]” 時
必須處理掉最近一組 “[“, “]” 中的 cur_s
　　　　　和與之相配的最近一個 “[” 前的 alphas 和 digits (即 stack[-1])

Time Complexity:
\begin{align}
& O(max\{ d_i \} \cdot len(s)) \\
& \text{※ }d_i: \text{We iterate } d_i \text{ times to decode each pattern.}
\end{align}
Space Complexity: O(m * n)
　m: number of letters (a-z)
　n: number of digits (0-9)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def decodeString(self, s: str) -> str:
    stack = []
    cur_s, d = '', ''
    for c in s:
      if c.isdigit():
        d += c
      elif c.isalpha():
        cur_s += c
      elif c=='[':
        stack.append((cur_s, int(d)))
        cur_s, d = '', ''
      elif c==']':
        p, n = stack.pop()
        cur_s = p + cur_s * n
            
    return cur_s

範例

1. s = “3[a]2[bc]”
   1. 3 → cur_s: “”, d: 3, stack: [] []
   2. [ → cur_s: “”, d: 0, stack: [3] [“”]
   3. a → cur_s: “a“, d: 0, stack: [3] [“”]
   4. ] → cur_s: “aaa“, d: 0, stack: [] []
   5. 2 → cur_s: “aaa”, d: 2, stack: [] []
   6. [ → cur_s: “”, d: 0, stack: [2] [“aaa”]
   7. bc → cur_s: “bc“, d: 0, stack: [2] [“aaa”]
   8. ] → cur_s: “aaabcbc“, d: 0, stack: [] []
2. s = “3[a2[c]]
   1. 3 → cur_s: “”, d: 3, stack: [] []
   2. [ → cur_s: “”, d: 0, stack: [3] [“”]
   3. a → cur_s: “a“, d: 0, stack: [3] [“”]
   4. 2 → cur_s: “a”, d: 2, stack: [3] [“”]
   5. [ → cur_s: “”, d: 0, stack: [3, 2] [“”, “a”]
   6. c → cur_s: “c“, d: 0, stack: [3, 2] [“”, “a”]
   7. ] → cur_s: “acc”, d: 0, stack: [3] [“”]
   8. ] → cur_s: “accaccacc“, d: 0, stack: [] []
3. 2[abc]3[cd]ef
   1. 2 → cur_s: “”, d: 2, stack: [] []
   2. [ → cur_s: “”, d: 0, stack: [2] [“”]
   3. abc → cur_s: “abc“, d: 0, stack: [2] [“”]
   4. ] → cur_s: “abcabc“, d: 0, stack: [] []
   5. 3 → cur_s: “abcabc”, d: 3, stack: [] []
   6. [ → cur_s: “”, d: 0, stack: [3] [“abcabc”]
   7. cd → cur_s: “cd“, d: 0, stack: [3] [“abcabc”]
   8. ] → cur_s: “abcabccdcdcd“, d: 0, stack: [] []
   9. ef → cur_s: “abcabccdcdcdef“, d: 0, stack: [] []

Last Updated on 2023/08/16 by A1go