摘要：用棧暫存的邏輯與遞歸基本一致，可以理解為用遞歸實現棧。沒有棧這種數據結構，可以用數組或雙端隊列可以只用一個棧以元組的形式重復次數和字符串，如利用棧初始化數據結構遞歸字符串入棧刷新計算重復次數可直接操作字符串真的很方便。

給定一個經過編碼的字符串，返回它解碼后的字符串。
Given an encoded string, return its decoded string.

編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數。
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

此外，你可以認為原始數據不包含數字，所有的數字只表示重復的次數 k ，例如不會出現像 3a 或 2[4] 的輸入。
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won"t be input like 3a or 2[4].

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

? 這道題類似我們之前做過的一道題：有效的括號: https://mp.weixin.qq.com/s/Sm1S26EgR-dC75hrhVnZGQ

只不過""有效的括號"" [] 內多了一些字符串需要操作。我們同樣可以用數據結構棧來解題，，能用棧解決的題目大部分都可以用遞歸解決，兩者邏輯基本相同：

輸入:"3[a2[c]]"
初始化棧: 棧nums 存要重復的次數k,棧str 存字符串

遍歷字符串:
指針指向字符"3",為數字
num暫存數字3

繼續遍歷,遇到字符"["
循環次數num入棧nums，空字符串res入棧str
nums: 3        res: ""
num置為0，str置空

繼續遍歷,遇到字符"a",為字母
空字符串res拼接字母"a",res="a"

繼續遍歷,遇到字符"2",為數字
num暫存數字2

繼續遍歷遇到字符"["
num入棧nums,res入棧str
nums: 3 -> 2    str: "" -> "a"
num置為0，str置空

繼續遍歷,遇到字符"c",為字母
空字符串res拼接字母"c",res="c"

繼續遍歷遇到字符"]"
nums彈出棧頂元素：當前字符串重復次數2
res = res*2 = "cc"
str彈出棧頂元素"a"與res拼接并入棧:
res = "a"+"cc"="acc"
str: "" -> "acc"

繼續遍歷遇到字符"]"
nums彈出棧頂元素：當前字符串重復次數3
res = res*3 = "accaccacc"
str彈出棧頂元素空字符串""與res拼接并入棧:
res=""+"accaccacc"="accaccacc"
str: "accaccacc"

結束返回res

注意：

由于重復次數可能大于10，所以暫存數字時要適當處理，如 num*10+當前數字

在c++里可以直接修改拼接字符，但Java不支持運算符重載，可以借助 StringBuilder 或 StringBuffer 類。

用棧暫存的邏輯與遞歸基本一致，可以理解為用遞歸實現棧。

python沒有棧這種數據結構，可以用 list() 數組或雙端隊列 deque()

python可以只用一個棧以元組的形式重復次數和字符串，如(num,res)

Java：

class Solution {
    public String decodeString(String s) {
        //初始化數據結構
        Stack str = new Stack<>();
        Stack nums = new Stack<>();
        StringBuilder res = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {//遞歸字符串
            if (c == "[") {
                str.push(res);//入棧
                nums.push(num);
                num = 0;//刷新num、res
                res = new StringBuilder();
            } else if (c == "]") {
                StringBuilder tmp = new StringBuilder();
                for (int i = nums.pop(); i > 0; i--) tmp.append(res);//res*3
                res = str.pop().append(tmp);
            } else if (c >= "0" && c <= "9") num = num * 10 + (c - "0");//計算重復次數
            else res.append(c);
        }
        return res.toString();
    }
}

Python：

可直接操作字符串真的很方便。py里有現成的判斷字符串的方法：

isdigit() 是否為只包含數字的字符串

isalpha() 是否為只包含字母的字符串

class Solution:
    def decodeString(self, s: str) -> str:
        #初始化數據結構
        stack, res, num = [], "", 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c.isalpha():
                res += c
            elif c == "[":
                #元組形式入棧
                stack.append((res, num))
                #刷新字符串和重復次數
                res, num = "", 0
            else:
                #如果c=="]",彈出字符串和重復次數
                last_str, this_num = stack.pop()
                res = last_str + this_num * res
        return res

Java：

將 s.length() 的值以參數傳遞，減少重復調用 length() 造成的時間損耗

class Solution {
    private int i = -1;//全局變量i，記錄字符數組指針位置
    
    public String decodeString(String s) {
        return dfs(s.toCharArray(), s.length()).toString();
    }
    //遞歸函數
    private StringBuilder dfs(char[] chars, int len) {
        int num = 0;
        StringBuilder str = new StringBuilder();
        while (++i < len) {
            if (chars[i] >= "0" && chars[i] <= "9")
                num = num * 10 + (chars[i] - "0");
            else if (chars[i] == "[") {
                StringBuilder tmp = dfs(chars, len);//遞歸調用
                while (--num >= 0) str.append(tmp);//重復字符串res=res*num
                num = 0;
            } else if (chars[i] == "]") return str;
            else str.append(chars[i]);
        }
        return str;
    }
}

Python：

class Solution:
    i = -1
    #遞歸函數，可以直接操作字符串就無需再建一個dfs輔助函數
    def decodeString(self, s: str) -> str:
        res, num = "", 0
        while self.i < len(s) - 1:
            self.i += 1
            if s[self.i].isdigit():
                num = num * 10 + int(s[self.i])
            elif s[self.i].isalpha():
                res += s[self.i]
            elif s[self.i] == "[":
                #遞歸調用
                res += self.decodeString(s) * num
                num = 0
            elif s[self.i] == "]":
                return res
        return res

歡迎關注微.信公.眾號：愛寫Bug