20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([)]”
输出：false

示例 5：
输入：s = “{[]}”
输出：true

遍历给定的字符串 ，当遇到一个左括号时，会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此可以将这个左括号放入栈顶。
当遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串无效。
为了快速判断括号的类型，可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 若遇到右括号 弹出栈顶元素，进行比较，反之入栈
        if (map.containsKey(c)) {
            char topElement = stack.empty() ? '#' : stack.pop();
            // 若栈顶元素和右括号对应的左括号类型不匹配，则不是有效括号字符串
            if (topElement != map.get(c)) {
                return false;
            }
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

优化一下：可以提前判断一下字符串长度，如果是奇数，那么必定不是有效括号字符串

 public boolean isValid(String s) {
     // 奇数长度必定不是有效括号字符串
     if (s.length() % 2 == 1) {
         return false;
     }
     Map<Character, Character> map = new HashMap<>();
     map.put(')', '(');
     map.put('}', '{');
     map.put(']', '[');
     Stack<Character> stack = new Stack<>();
     for (int i = 0; i < s.length(); i++) {
         char c = s.charAt(i);
         // 若遇到右括号 弹出栈顶元素，进行比较，反之入栈
         if (map.containsKey(c)) {
             char topElement = stack.empty() ? '#' : stack.pop();
             // 若栈顶元素和右括号对应的左括号类型不匹配，则不是有效括号字符串
             if (topElement != map.get(c)) {
                 return false;
             }
         } else {
             stack.push(c);
         }
     }
     return stack.isEmpty();
 }