Problem: 394. 字符串解碼
給定一個經過編碼的字符串，返回它解碼后的字符串。
編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數。
你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。
此外，你可以認為原始數據不包含數字，所有的數字只表示重復的次數 k ，例如不會出現像 3a 或 2[4] 的輸入。

整體思路

這段代碼旨在解決一個涉及嵌套結構的 字符串解碼 (Decode String) 問題。編碼規則是 k[encoded_string]，表示 encoded_string 這部分內容重復 k 次。由于括號可以嵌套，例如 3[a2[c]]，這個問題具有天然的遞歸或棧式結構。

該算法巧妙地采用了 雙棧（Two Stacks） 的迭代方法來處理這種嵌套關系，避免了顯式遞歸。

1. 數據結構選擇：

   • strStack (字符串棧): 用于保存遇到 [ 之前的字符串部分。當解碼一個內部括號時，棧頂的字符串就是其解碼結果需要拼接的前綴。
   • numStack (數字棧): 用于保存與 [ 對應的重復次數 k。
   • StringBuilder curr: 用于高效地構建當前正在處理的、位于同一嵌套層級的字符串。
   • int k: 一個臨時變量，用于解析可能由多位數字組成的重復次數。

2. 核心遍歷與狀態管理邏輯：

   • 算法通過單次遍歷輸入字符串 s 的每個字符來驅動。根據字符的類型，執行不同的狀態轉換：
     • 遇到數字 ('0'-'9'): 將其累加到 k 變量中。k = k * 10 + c - '0' 這個技巧可以正確地解析多位數（如 “10”, “123”）。
     • 遇到左括號 ('['): 這標志著進入了一個新的、更深的嵌套層級。此時，必須“保存”當前層級的狀態，以便稍后恢復。
       • 將當前的重復次數 k 壓入 numStack。
       • 將當前已經構建好的字符串 curr 壓入 strStack。
       • 重置 k 和 curr，為新的嵌套層級做準備。
     • 遇到右括號 (']'): 這標志著一個嵌套層級的結束。此時，需要“恢復”上一層級的狀態并執行解碼。
       • 從 numStack 彈出重復次數 repeat。
       • 從 strStack 彈出上一層級的字符串前綴 prev。
       • 將當前 curr 所代表的字符串重復 repeat 次。
       • 將重復后的字符串與前綴 prev 合并，形成新的 curr。這就完成了從內層到外層的解碼與合并。
     • 遇到字母 (else): 這是一個普通字符，直接追加到當前層級的字符串構建器 curr 的末尾。

3. 返回結果：

   • 當遍歷完整個輸入字符串后，curr 中就包含了完全解碼后的最終字符串，將其返回即可。

這個雙棧方法優雅地模擬了遞歸調用過程：[ 相當于遞歸深入，] 相當于遞歸返回。

完整代碼

class Solution {/*** 解碼一個按特定規則編碼的字符串。* @param s 編碼后的字符串，例如 "3[a2[c]]"* @return 解碼后的字符串，例如 "accaccacc"*/public String decodeString(String s) {// strStack: 用于保存遇到'['之前的字符串部分，作為解碼時的前綴。Deque<String> strStack = new ArrayDeque<>();// numStack: 用于保存'['前的重復次數 k。Deque<Integer> numStack = new ArrayDeque<>();// k: 臨時變量，用于解析可能的多位數字。int k = 0;// curr: 一個 StringBuilder，用于高效地構建當前嵌套層級的字符串。StringBuilder curr = new StringBuilder();// 遍歷輸入字符串的每一個字符for (char c : s.toCharArray()) {if (c >= '0' && c <= '9') {// 如果是數字，更新 k 的值。k * 10 的技巧可以處理多位數。k = k * 10 + c - '0';} else if (c == '[') {// 如果是左括號，表示進入新的嵌套層級。// 1. 將當前的重復次數 k 壓入數字棧numStack.push(k);// 2. 將當前已構建的字符串 curr 壓入字符串棧strStack.push(curr.toString());// 3. 重置 k 和 curr，為新層級做準備k = 0;curr = new StringBuilder();} else if (c == ']') {// 如果是右括號，表示一個嵌套層級結束，需要解碼。// 1. 彈出該層級對應的重復次數int repeat = numStack.pop();// 2. 彈出上一層的字符串前綴String prev = strStack.pop();// 3. 將當前層級的字符串(curr)重復指定次數String repeated = curr.toString().repeat(repeat);// 4. 將重復后的字符串與前綴合并，更新為新的當前層字符串curr = new StringBuilder(prev + repeated);} else {// 如果是普通字母，直接追加到當前層級的字符串中curr.append(c);}}// 循環結束后，curr 中即為最終完全解碼的字符串return curr.toString();}
}

時空復雜度

時間復雜度：O(N + M)

1. N 的部分：算法的主體是一個 for 循環，它遍歷輸入字符串 s 一次。設 s 的長度為 N。這個掃描過程本身是 O(N) 的。
2. M 的部分：
   • 在循環內部，最耗時的操作是 curr.toString().repeat(repeat) 和隨后的字符串拼接。
   • 這些操作的總成本不取決于 N，而是取決于最終解碼后字符串的長度，我們稱之為 M。
   • 每一個最終生成在結果字符串中的字符，都是通過 append 或 repeat 操作產生的。所有這些生成操作的總和與最終字符串的長度 M 成正比。
3. 綜合分析：
   • 總時間復雜度是掃描輸入字符串的時間加上生成輸出字符串的時間。
   • 因此，最終的時間復雜度為 O(N + M)，其中 N 是輸入字符串的長度，M 是輸出字符串的長度。

空間復雜度：O(N) 或 O(M)

1. 主要存儲開銷：空間主要由兩個棧 strStack 和 numStack 以及 StringBuilder curr 占用。
2. 空間大小：
   • numStack 的大小與嵌套深度成正比，最多為 O(N)。
   • strStack 存儲的是中間的字符串片段。在最壞的情況下，例如 2[a2[b2[c...]]]，棧中存儲的字符串總長度可能與最終輸出字符串的長度 M 相關。
   • 然而，在更典型的情況下，例如 a[b[c...]]，棧中存儲的字符串總長度（“a”, “ab”, “abc” …）可以被輸入長度 N 所限制。
   • 考慮到各種情況，一個比較合理的上界是 O(N + M)，但通常在分析中會簡化為 O(N) 或 O(M)，這取決于哪一個在特定用例中是主導因素。在大多數面試場景下，將其分析為 O(N) 是被接受的，因為它與輸入的規模和結構直接相關。

綜合分析：
算法的輔助空間復雜度主要由棧的內容決定，其大小與輸入的嵌套深度和字符串片段長度有關。一個合理的估計是 O(N)。