問(wèn)題鏈接

#### 20. 有效的括號(hào)

問(wèn)題描述

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

有效字符串需滿足：

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

提示：

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

示例

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

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

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

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

解題思路

核心：棧

• 方法1: 替換字符串
  不停的用()、[]、{}對(duì)原字符串進(jìn)行替換，替換成空字符串；直到無(wú)法替換，看一下當(dāng)前字符串是不是空，不如是空，返回true；反之，存在多余的括號(hào)，返回false。

• 方法2: 棧
  首先，檢驗(yàn)一下字符串的長(zhǎng)度是不是2的整數(shù)倍，如果不是，肯定有括號(hào)無(wú)法進(jìn)行匹配，直接結(jié)束；
  然后，新建一個(gè)棧，遍歷原字符串：如果遇到左括號(hào)，就往棧里扔；如果遇到右括號(hào)，取出棧頂元素進(jìn)行匹配校驗(yàn)，校驗(yàn)失敗就直接返回false結(jié)束；
  最后，校驗(yàn)一下棧是否為空，如果為空，表示全都匹配完了，返回true；反之，返回false。

代碼示例（JAVA）

這里僅展示棧的解法，其中，用了一個(gè)map來(lái)維護(hù)括號(hào)對(duì)。

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            put(')', '(');
            put('}', '{');
            put(']', '[');
        }};
        for (char c : s.toCharArray()) {
            if (!map.keySet().contains(c)) {
                stack.push(c);
            } else {
                if (stack.empty() || stack.pop() != map.get(c)) {
                    return false;
                }
            }
        }
        return stack.empty();
    }
}