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

題目描述

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

有效字符串需滿足：
(1) 左括號(hào)必須用相同類型的右括號(hào)閉合。
(2) 左括號(hào)必須以正確的順序閉合。
注意：空字符串可被認(rèn)為是有效字符串。

示例 1:
輸入: "()"
輸出: true

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

示例 3:
輸入: "(]"
輸出: false

示例 4:
輸入: "([)]"
輸出: false

示例 5:
輸入: "{[]}"
輸出: true

算法思想

這題是比較簡(jiǎn)單的括號(hào)匹配問(wèn)題，可以使用棧來(lái)實(shí)現(xiàn)。
遍歷字符串，如果當(dāng)前字符為左括號(hào)，則進(jìn)行壓棧操作；否則，則進(jìn)行出棧操作，同時(shí)判斷出棧元素是否為當(dāng)前字符對(duì)應(yīng)的左括號(hào)，如果不是，則說(shuō)明括號(hào)不匹配。
如果最后棧為空，說(shuō)明字符串中的括號(hào)全部匹配成功。

考慮幾種特殊的情況：

• 如果字符串的長(zhǎng)度為奇數(shù)，則肯定不滿足括號(hào)匹配條件，直接返回false
• 如果字符串為空，則直接返回true

代碼實(shí)現(xiàn)

class Solution {
    private static final Map<Character, Character> map = new HashMap<>(){
        {
            put('(',')');
            put('[', ']');
            put('{', '}');
        
        }
    };

    public boolean isValid(String s) {
        int i = 0;
        int len = s.length();

        // 如果字符串的長(zhǎng)度為奇數(shù)，則肯定不滿足條件
        if (len % 2 == 1) {
            return false;
        }

        List<Character> stack = new LinkedList<>();
        while(i < len) {
            // 如果當(dāng)前字符為左括號(hào)，則壓棧，否則出棧
            if (map.containsKey(s.charAt(i))) {
                stack.add(s.charAt(i));
            } else {
                // 如果棧為空，說(shuō)明當(dāng)前字符沒(méi)有與之匹配的左括號(hào)，直接返回false
                if (stack.size() == 0) {
                    return false;
                }
                // 如果壓棧的左括號(hào)對(duì)應(yīng)的右括號(hào)為當(dāng)前字符，則匹配成功，否則匹配失敗
                if (map.get(stack.remove(stack.size() - 1)) != s.charAt(i)) {
                    return false;
                }
            }
            i ++;
        }

        return stack.size() == 0;
    }
}