LeetCode 筆記 - 394. Decode String

Posted on

題目在此 394. Decode String

給定一個編碼過的字串，請將其解碼回原本的字串。編碼規則為 k[encoded_string]，表示 encoded_string 會被重複 k 次。
k 是一個正整數，且 encoded_string 只會包含小寫英文字母。你可以假設輸入的字串是有效的，且不會有額外的空白字元，且原始資料不會被重複編碼。

例如：

  • s = "3[a]2[bc]"，會回傳 "aaabcbc"
  • s = "3[a2[c]]"，會回傳 "accaccacc"

解題思維

這題可以利用 Stack 來解決，主要是透過 Stack 來儲存目前的字串和數字，當遇到 ] 時，就將 Stack 中的元素彈出來，並進行解碼。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def decodeString(self, s: str) -> str:

        # step1: walk s, find digits and substrings store to a stack,
        # step2: if substring is closed (meets "]"), pop the digit and decode
        # step3: return result
        # time complexity: O(n^2)
        # space complexity: O(n)

        stack = []

        for c in s:

            if c == ']':
                cur_s = ''

                while not stack[-1].isdigit():
                    cur_s = stack.pop() + cur_s
                    
                # pop the '['
                cur_s = cur_s[1:]

                cur_int = ''
                while stack and stack[-1].isdigit():
                    cur_int = stack.pop() + cur_int

                cur_int = int(cur_int)

                stack.append(cur_s * cur_int)
                continue

            stack.append(c)

        return ''.join(stack)

也許你也會想看看