【LittleDuck_LeetCodeNote】20 - Valid Parentheses

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。

A realistic, brightly colored interior home-style drawing in blue tones of a software engineer. - Leonardo.ai

Question and Hints

An input string is valid if:

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

• 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;
    }
}

⏰ Runtime: 2 ms (86.51 %)

📦 Memory: 40.4 MB (83.13 %)

Upgrade Solution

more clear and faster.

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

• 可以直接用 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();
    }
}

⏰ Runtime: 1 ms (%)

📦 Memory: 40.9 MB (25.79 %)

Bonus Solution:

the fastest, no stack.

💡 一樣的邏輯，只是這個寫法是不使用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;
    }
}

⏰ Runtime: 0 ms (100 %)

📦 Memory: 40.1 MB (96.48 %)