給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

• 左括號(hào)必須用相同類型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。

示例 1：
輸入：s = "()"
輸出：true

示例 2：
輸入：s = "()[]{}"
輸出：true

示例 3：
輸入：s = "(]"
輸出：false

示例 4：
輸入：s = "([)]"
輸出：false

示例 5：
輸入：s = "{[]}"
輸出：true

提示：
1 <= s.length <= 104
s 僅由括號(hào) '()[]{}' 組成

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-parentheses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路及方法

比較經(jīng)典的算法，用棧去匹配。之前先預(yù)先判斷，如果字符串長度為奇數(shù)則肯定不滿足。

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            // 空棧字符入棧
            if (stack.isEmpty()) {
                stack.push(cur);
            } else {
                char top = stack.peek();
                // 括號(hào)匹配則棧頂字符出棧，否則當(dāng)前字符入棧
                if (top == '(' && cur == ')') stack.pop();
                else if (top == '[' && cur == ']') stack.pop();
                else if (top == '{' && cur == '}') stack.pop();
                else stack.push(cur);
            }
        }
        
        return stack.isEmpty();
    }
}

結(jié)果如下：