原文題目

Given an encoded string, return its decoded string.

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; there are no extra white spaces, square brackets are well-formed, etc. 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 will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10^5.

題目摘要

1. 問題描述：給定一個編碼字串k[encoded_string]（表示 encoded_string 需要重複 k 次），回傳處理後的字串。
2. 輸入：一個編碼字串，包含數字、字母和中括號。
3. 輸出：處理後的完整字串。

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

解題思路

1. 使用堆疊（Stack）：
   • 我們可以用堆疊來處理這樣的結構。當遇到 [ 時，我們可以將前面的數字和字串分別存入堆疊中；當遇到 ] 時，則從堆疊中取出相應的部分進行重複和拼湊。
2. 逐字元處理：
   • 當遇到數字時，將它完整讀取出來，這代表接下來的部分需要重複的次數。
   • 當遇到 [ 時，將目前的數字和字串存入堆疊，準備處理內部的子字串。
   • 當遇到 ] 時，從堆疊中取出上次存入的數字和字串，將當前的子字串重複多次，並和之前的部分拼接。
3. 邊界條件： 因為題目保證了輸入是有效的，因此我們不需要考慮不合法的輸入情況。

程式碼

class Solution {
    public String decodeString(String s) {
        //定義兩個堆疊：一個用來存字串，另一個用來存重複次數k
        Stack<String> stringStack = new Stack<>();
        Stack<Integer> kStack = new Stack<>();
        //用StringBuilder來累積當前字串：提高效能固非使用String
        StringBuilder p = new StringBuilder();
        int k = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i); //取出當前字元
            //如果是數字，累積當前的重複次數k
            if (Character.isDigit(ch)) {
                //將數字字元轉換為整數，並累積形成完整的數字
                k = k * 10 + (ch - '0');
            } 
            //如果遇到左括號 '[', 開始新的子字串
            else if (ch == '[') {
                //將當前的重複次數k和已經處理的字串p加入堆疊
                kStack.push(k);
                stringStack.push(p.toString());
                //重置當前字串為空，準備處理新的子字串
                p = new StringBuilder();  
                k = 0; //重置k為0，準備下一次的數字累積
            } 
            //如果遇到右括號 ']', 表示一個完整的子字串結束
            else if (ch == ']') {
                //從堆疊中取出對應的重複次數和字串
                int repeatTimes = kStack.pop();
                StringBuilder temp = new StringBuilder(stringStack.pop());
                //將當前的字串p重複repeatTimes次，並加到temp中
                for (int j = 0; j < repeatTimes; j++) {
                    temp.append(p);
                }
                //更新當前字串p為重複拼湊後的結果
                p = temp;  
            } 
            //如果是字母，直接將其加入到當前字串p中
            else {
                p.append(ch);
            }
        }
        //最後回傳完整字串
        return p.toString();
    }
}

結論： 在寫這題前我先觀看了leetcode上許多網友對於這題給出的程式碼，一開始看到對於p這個用來存放累積子字串使用方法為StringBuilder()而非string的變數型態感到很疑惑。一查之後才發現，相較於使用string，使用StringBuilder()允許在不創建新物件的情況下修改同一個字串內容。每次 append() 操作只是在原始字串的基礎上添加新內容，其效率會比string 做拼湊要高得多。果然，即使身為正在學習資訊科系的我，也仍然有無窮無盡的茫茫程式海需要去學習、多看、多聽！