LeetCode 20：有效的括号 Valid Parentheses

給定一個隻包括

'('

，

')'

'{'

'}'

'['

']'

的字元串，判斷字元串是否有效。

Given a string containing just the characters

'('

,

')'

'{'

'}'

'['

and

']'

, determine if the input string is valid.

有效字元串需滿足：

1. 左括号必須用相同類型的右括号閉合。
2. 左括号必須以正确的順序閉合。

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.

注意空字元串可被認為是有效字元串。

Note that an empty string is also considered valid.

示例 1:

輸入: "()"
輸出: true           

示例 2:

輸入: "()[]{}"
輸出: true           

示例 3:

輸入: "(]"
輸出: false           

示例 4:

輸入: "([)]"
輸出: false           

示例 5:

輸入: "{[]}"
輸出: true           

解題思路：

很簡單的題，将字元串每個字元壓入棧，簡單判斷即可。如：

輸入: "{[]}"
初始棧為空，'{' 入棧
下一個字元
棧頂元素 '{'與 '[' 不比對，'[' 入棧
下一個字元
棧頂元素 '['與 ']' 比對，'[' 出棧
下一個字元
棧頂元素 '{'與 '}' 比對，'}' 出棧
結束，棧為空，傳回 True           

關鍵在于判斷字元是否比對，比對的标準是相反的括号字元，并非相同字元。可以用 switch 判斷三種括号字元，或者三個 if 語句，再或者可以用散清單映射括号關系。

Java：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();//初始化棧
        for (char b : s.toCharArray()) {
            switch (b) {
                case '(': {
                    stack.push(')');
                    break;
                }
                case '{': {
                    stack.push('}');
                    break;
                }
                case '[': {
                    stack.push(']');
                    break;
                }
                default: {//不比對的情況傳回false
                    if (stack.isEmpty() || stack.pop() != b) {
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();//棧為空則證明全部比對，傳回true，否則傳回false
    }
}           

Python:

注：python中沒有 switch...case... 語句，官方讓用 if 判斷代替...

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == '[':
                stack.append(']')
            elif c == '(':
                stack.append(')')
            elif c == '{':
                stack.append('}')
            elif len(stack) == 0 or stack.pop() != c:
                return False
        return len(stack) == 0           

歡迎關注微.信公.衆号：愛寫Bug