leetcode_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" 示例 3： 輸入：s = "2[abc]3[cd]ef" 輸出："abcabccdcdcdef" 示例 4： 輸入：s = "abc3[cd]xyz" 輸出："abccdcdcdxyz"

核心程式碼

python class Solution: def decodeString(self, s: str) -> str: stack,res,count = [],"",0 for c in s: if "0" <= c <= "9": count = count * 10 + int(c) elif c == "[": stack.append([res,count]) res,count = "",0 elif c == "]": tmpRes,tmpCount = stack.pop() res = tmpRes + tmpCount * res else: res += c return res

解題思路：這種題看到的第一眼就知道必定用棧去解，第一個判斷是不是數字，是數字，之前要是還有數字的話，就是向前進位，當我們碰到[的時候,我們將之前的數字和字元先儲存在棧中，先處理後面優先順序高的內層，當我們碰到]的時候，說明內層已經處理完畢，我們將之前儲存進去的資料彈出來，進行外層的處理，不斷的拼接，最終得到我們解碼後的字串。