【LittleDuck_LeetCodeNote】20 - Valid Parentheses

Question and Hints

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

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 %)