【LittleDuck_LeetCodeNote】20 - Valid Parentheses

Question and Hints

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Input: s = "()"
Output: true

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

First Solution

💡 相當經典的Stack考題，因為括號一定是成雙成對，而且不能穿插，
所以假如右括號的前一個字元不是對應的左括號，就是有問題的。
成對的括號就全部pop掉，理想情況下最後Stack會pop掉全部的括號，
這時就可以回傳true，除此之外的異常都要回傳false。

注意：第一個字元如果就是右括號，那就直接回傳false，
因為這一開始就有問題。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk = new Stack<>();

        for(int i=0; i<s.length(); i++){
	　　// avoid first Parentheses is valid rightnow.
            if(stk.empty()){
                if(s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}')
                    return false;
            }

            stk.push(s.charAt(i));
            switch(s.charAt(i)){
                case ')':
                    stk.pop();
                    if(!(stk.pop().equals('(')))
                        return false;
                    break;

                case ']':
                    stk.pop();
                    if(!(stk.pop().equals('[')))
                        return false;
                    break;

                case '}':
                    stk.pop();
                    if(!(stk.pop().equals('{')))
                        return false;
                    break;
            }
        }
        if(stk.empty())
            return true;
        
        return false;
    }
}

Upgrade Solution

💡 邏輯是一樣的，只是這寫法更乾淨也更快：

• 可以直接用 toCharArray() 將字串轉成陣列，用Enhance for loop ( for-each, 又稱加強版for迴圈 )去做檢查。
• 左括號也進行判斷再push，可以少一點多餘的檢查。
• 右括號push進去前先檢查peek，可以少一次pop和push。
• 最後 Stack.empty()本身就會回傳true或false，所以不用多此一舉加上if，直接回傳Stack.empty() 就好。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.empty()) {
                    return false;
                }
                if (c == ')' && stack.peek() == '(') {
                    stack.pop();
                } else if (c == '}' && stack.peek() == '{') {
                    stack.pop();
                } else if (c == ']' && stack.peek() == '[') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.empty();
    }
}

Bonus Solution:

💡 一樣的邏輯，只是這個寫法是不使用Java內建的Stack，
而是用陣列結合index的操作去時做出Stack的效果，
雖然閱讀起來不太直觀，但就速度上來說是最快的。

class Solution {
    public boolean isValid(String s) {
        char[] word = new char[s.length()];
        int wordIdx = -1;
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                word[++wordIdx] = ch;
            } else {
                if (wordIdx < 0) {
                    return false;
                }
                char ch2 = word[wordIdx--];
                if ( ch == ')' && ch2 != '(' ||
                     ch == '}' && ch2 != '{' ||
                     ch == ']' && ch2 != '[') {
                    return false;
                }
            }
        }
        return wordIdx < 0;
    }
}