字元串解碼（python）

394.字元串解碼

• 題目描述
• 解題思路
• 代碼
• 時間複雜度分析

題目描述

➡ 題目連結 ⬅

給定一個經過編碼的字元串，傳回它解碼後的字元串。

編碼規則為: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重複 k 次。注意 k 保證為正整數。

你可以認為輸入字元串總是有效的；輸入字元串中沒有額外的空格，且輸入的方括号總是符合格式要求的。

此外，你可以認為原始資料不包含數字，所有的數字隻表示重複的次數 k ，例如不會出現像 3a 或 2[4] 的輸入。

示例1：

輸入：s = "3[a]2[bc]"
輸出："aaabcbc"
           

示例2：

輸入：s = "3[a2[c]]"
輸出："accaccacc"
           

解題思路

• 本題存在括号中嵌套括号的情況，故需要從最内部的括号開始生成字元串，即利用棧的先入後出特性解題。
• 算法流程：
  • 建立棧

    stack

    ；建立

    num

    ，初始值為 ，用于存儲數字；建立

    res

    ，初始值為

    ''

    ，用于存儲臨時結果。周遊字元串

    s

    中的每一個字元

    i

    • 當

      i

      為數字時，将數字字元轉化為int型，做下列後續倍數計算：

      num = 10 * num + int(i)

    • 當

      i

      為字母時，将字母添加到res尾部
    • 當

      i

      為

      [

      時，将目前的res和num存入棧中，并将num和res分别置0置空
    • 當

      i

      為

      ]

      時，進行一次出棧操作，拼接字元串

      res = cur_res + cur_num * res

      ，其中：

      • cur_res

        為上一個

        [

        到目前

        [

        的字元串

      • cur_num

        為目前

        [

        到

        ]

        的字元串重複倍數
  • 傳回字元串

    res

代碼

class Solution:
    def decodeString(self, s):
        num = 0
        stack = []
        res = ''
        for i in s:
            if '0' <= i <= '9':
                num = 10 * num + int(i)
            elif i == '[':
                stack.append((res, num))
                num = 0
                res = ''
            elif i == ']':
                cur_res, cur_num = stack.pop()
                res = cur_res + cur_num * res
            else:
                res += i
        return res
           

時間複雜度分析

• 使用一次

  for

  循環周遊字元串

  s

• 時間複雜度為O(N)