20. Valid Parentheses — 一樣是兩周前的題目，還是WA

明知道是用stack，但還是錯了，小地方又沒注意到

20. Valid Parentheses

今天複習第20題，還記得第一次做到這題的時候，看到解答用的是stack，完美解決這個問題拍手叫絕，深刻的記得只要配對括號就用stack準沒錯。於是埋頭就寫，洋洋灑灑的寫完，五分鐘，Run。正準備按submit的時候，compile當頭棒喝，原來是break忘了加分號。小問題，補上，Run，滑鼠又控制不住自己往submit的地方移動，很好，又是compile error，這次是isEmpty忘了加括號，再來一次，runtime error，stack沒東西，但我卻pop了，補上!isEmpty，然後直接check stack是不是empty，回傳該boolean，以為終於要成功了，有個測資錯了。

s = “]”

我的Code (錯的)

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    // Iterate the string as characters
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (!stack.isEmpty()){
            char part = stack.pop();
            switch (c) {
                case ')':
                    if (part != '(') return false;
                    break;
                case ']':
                    if (part != '[') return false;
                    break;
                case '}':
                    if (part != '{') return false;
                    break;
            }
        }
    }
    return stack.isEmpty();
}

那個測資完美的避開了我的check，想了十分鐘還是想不到怎麼改比較好，所以看了一下LC的討論區，有的人用peek，有的直接看到如果不是(, [, {然後stack如果是empty的直接return false。覺得這個方法簡潔明瞭，因為會到([{這個條件下那代表一定有需要匹配的括號，但因為stack是空的根本沒辦法匹配，所以直接回傳就行了。(我之前寫的是用peek方法避開stack是空的狀況)

方法

1. 建立一個stack

2. 循環string的每個字

3. 看到([{的時候就直接push

4. 當看到如上三個符號之外的，先看看stack是否是空的，如果是的話表示沒有左括號可以匹配，所以直接回傳false

5. 接著就看是否是匹配的括號就行了

AC的Code

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    // Iterate the string as characters
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (stack.isEmpty()){ // 多加的
            return false;
        } else {
            char part = stack.pop();
            switch (c) {
                case ')':
                    if (part != '(') return false;
                    break;
                case ']':
                    if (part != '[') return false;
                    break;
                case '}':
                    if (part != '{') return false;
                    break;
            }
        }
    }
    return stack.isEmpty();
}

多加了一個判斷就成功AC

這次寫題有以下幾點問題:

• 題目沒看，思路沒有想，直接寫(因為之前做過，覺得可以一次寫出來)

• 測資沒想清楚 (下次應該要自己生一些test case測試看看，尤其是錯的和corner case狀況)

• 寫語句的時候很粗心，忘加分號，忘加function的括號

總結來說，還是爛得要死，繼續加油