題目
#

題目簡述
#

給定一個編碼的字串，解碼並返回解碼後的字串。編碼規則為 k[encoded_string]，表示其中的 encoded_string 正好重複 k 次。

範例
#

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: "a" 重複 3 次，"bc" 重複 2 次。

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: "c" 重複 2 次得到 "cc"，然後 "acc" 重複 3 次。

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: "abc" 重複 2 次，"cd" 重複 3 次，加上 "ef"。

解題思路
#

這題要求解碼嵌套格式的字串，例如 3[a2[c]] 需要展開成 accaccacc。

解法：使用堆疊（Stack）模擬展開過程

數字處理：當遇到數字時，累計數字值，表示接下來的字串需要重複的次數。
左括號 [：遇到 [ 時，將當前數字與已解析的字串推入堆疊，開始處理新的子字串。
右括號 ]：遇到 ] 時，從堆疊中取出數字與之前的字串，將當前處理的子字串重複相應次數後加回。
字母處理：如果是普通字母，則直接加入當前字串。

這種方法確保能夠處理多層嵌套結構，例如 3[a2[c]]。

例子說明
#

s = "3[a2[c]]"

初始情況：sb = ""，stNum = []，stStr = []，n = 0

處理字符 ‘3’：
- 是數字，n = n * 10 + (3 - '0') = 3
處理字符 ‘[’：
- 是左括號，stNum.push(3)，n = 0
- stStr.push("")，sb = ""
處理字符 ‘a’：
- 是字母，sb.append('a')，sb = "a"
處理字符 ‘2’：
- 是數字，n = n * 10 + (2 - '0') = 2
處理字符 ‘[’：
- 是左括號，stNum.push(2)，n = 0
- stStr.push("a")，sb = ""
處理字符 ‘c’：
- 是字母，sb.append('c')，sb = "c"
處理字符 ‘]’：
- 是右括號，cnt = stNum.pop() = 2
- temp = "c"，sb = stStr.pop() = "a"
- 重複 2 次：sb.append("c")，sb.append("c")
- sb = "acc"
處理字符 ‘]’：
- 是右括號，cnt = stNum.pop() = 3
- temp = "acc"，sb = stStr.pop() = ""
- 重複 3 次：sb.append("acc")，sb.append("acc")，sb.append("acc")
- sb = "accaccacc"
最終結果：
- 返回 "accaccacc"

完整程式碼
#

java

import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder(); // 當前處理的字串
        Stack<Integer> stNum = new Stack<>(); // 存儲重複次數的堆疊
        Stack<StringBuilder> stStr = new Stack<>(); // 存儲字串的堆疊
        int n = 0; // 當前累計的數字

        for (int i = 0; i < s.length(); i++) { // 遍歷字串中的每個字符
            if (Character.isDigit(s.charAt(i))) { // 如果是數字
                n = n * 10 + (s.charAt(i) - '0'); // 累計數字值
            } else if (s.charAt(i) == '[') { // 如果是左括號
                stNum.push(n); // 將數字推入堆疊
                n = 0; // 重置數字
                stStr.push(sb); // 將當前字串推入堆疊
                sb = new StringBuilder(); // 開始新的字串
            } else if (s.charAt(i) == ']') { // 如果是右括號
                int cnt = stNum.pop(); // 取出重複次數
                StringBuilder temp = sb; // 暫存當前字串
                sb = stStr.pop(); // 取出之前的字串
                while (cnt-- > 0) { // 重複指定次數
                    sb.append(temp); // 將字串加入
                }
            } else { // 如果是字母
                sb.append(s.charAt(i)); // 直接加入當前字串
            }
        }
        return sb.toString(); // 返回最終結果
    }
}