给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

Solution

参考：《算法小抄》5.9

• 利用哈希表和栈

# @lc code=start
class Solution:
    def isValid(self, s: str) -> bool:
        if not s: return True
        stack = []
        hashC = {')':'(', ']':'[', '}':'{'}
        
        for c in s:
            if c in {'(','[','{'}:
                stack.append(c)
            elif stack and hashC[c]==stack[-1]:
                stack.pop()
            else:
                return False
        return len(stack)==0
# @lc code=end

cpp

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        if(!s.size()) return true;
        if(s.size()%2==1) return false;
        stack<char> stack;
        unordered_map<char,char> mp = {
            {')', '('}, {']', '['}, {'}', '{'}
        };
        for(char c: s){
            // 力扣可能还不支持 contains (C++20) 。。。
            if(mp.find(c) != mp.end()){  
                if(stack.empty() || stack.top()!=mp[c])
                    return false;
                else 
                    stack.pop();
            }
            else 
                stack.push(c);
        }
        return stack.empty();
    }
};
// @lc code=end

参考：系统中处处都是栈的应用

• 在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

java

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

        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < len; ++i) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(')');
            } else if (ch == '{') {
                stack.push('}');
            } else if (ch == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.peek() != ch) {
                return false;
            } else {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}