有效的括号

题目链接

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

有效字符串需满足：

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

示例:

输入：s = "()"
输出：true

思路

解法一：

最先想到的方法，首先是设置一个 index=0，遇到左括号的时候 index+1,遇到右括号的时候 index-1,最后判断 index==0。但此方法不适用此题，因题目要求左括号必须以正确的顺序闭合，所以可以很容易想到使用栈来解决。

可以使用 map 存储左右括号的对应关系。

  1. 先定义一个 map，key 为右括号，val 为左括号。
  2. 若字符为左括号，则入栈，若为右括号，判断是否异常（栈为空或符号不匹配），则出栈。
  3. 判断最后的栈是否为空。
class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}};
        stack<char> stk; // 使用栈来存储左右括号
        for (char c: s) {
            if (pairs.count(c)) { // 若为右括号
                if (stk.empty() || stk.top() != pairs[c]) { // 若栈为空或符号不匹配，return false
                    return false;
                }
                stk.pop(); // 右括号出栈
            }else {
                stk.push(c); // 若为左括号，则入栈。
            }
        }
        return stk.empty();
    }
};

解法二：

不使用map，每次判断栈顶元素与字符的匹配关系。

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }
        stack<char> stk; // 使用栈来存储左右括号

        for (char c: s) {
            if (!stk.empty()){ // 栈不为空
                char t = stk.top(); 
                if (t == '(' && c == ')' // 判断栈顶元素与字符的匹配关系
                ||t == '[' && c == ']'
                || t == '{' && c == '}'){
                    stk.pop();
                    continue;
                }
            }
            stk.push(c);
        }
        return stk.empty();
    }
};