394. Decode String - Medium

前往題目

想法

• 看到括號第一直覺是用stack
• 可能可以用兩個stack，一個存數字，一個存符號

思路

這道題看了解答還是花了我兩小時左右，都在處理資料，而不是邏輯😂Java處理資料之間的轉換真的是麻煩

1. 遇到右括號以外的符號或數字的時候直接push到stack裡面就好
2. 遇到右括號就把[]裡的字符都存起來，然後再把數字k也存起來
3. 把字符複製k次存進結果
4. 繼續疊代直到把每個字符都檢查完

Code

主要參考了Neetcode大大和討論區的解答

利用stack的特性，可以很巧妙的把nested encoded string放一起然後複製，例如3[a2[c]]會變為accaccacc，演算法要能夠存好cc，然後遇到a的時候可以附在後面。原因就是因為前面的結果會push回同樣的stack

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack();

        // Look every character
        for (int i = 0; i < s.length(); ++i) {
            // An encoded string hasn't found
            if (s.charAt(i) != ']') {
                stack.push(s.charAt(i));
            } else { // Found
                StringBuilder substr = new StringBuilder("");

                // Store the string
                while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
                    substr.append(stack.pop());
                }
                // To the normal sequence
                substr.reverse();
                // Pop '['
                stack.pop();

                // Repeating times
                StringBuilder k = new StringBuilder("");
                // Store the numbers
                while (!stack.isEmpty() && 
                        Character.isDigit(stack.peek())) {
                    k.insert(0, stack.pop());
                }
                
                
                int times = Integer.parseInt(k.toString());
                // Add to the stack
                for (int j = 0; j < times; ++j) {
                    for (char c : substr.toString().toCharArray()){
                        stack.push(c);
                    }
                }

            }
        }

        StringBuilder res = new StringBuilder("");
        while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
            res.insert(0, stack.pop());
        }
        return res.toString();
    }
}

2024/04/29

• 看了code才想起解法

2024/08/19

• 知道用stack，但邏輯部分沒能在時間內想出來
• 看了之前寫的code後可以快速寫出和理解