有效的括号

题目描述

Category	Difficulty	Likes	Dislikes
algorithms	Easy (43.80%)	2226	-

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

有效字符串需满足：

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

示例 1：

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

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

---

程序代码

/*
 * @lc app=leetcode.cn id=20 lang=cpp
 *
 * [20] 有效的括号
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        //判断是否是偶数个 如果不是就直接返回false
        if(n % 2 == 1){
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        //创建符号栈
        stack<char> stk;

        for(char ch:s){
            //pairs.count(ch) 统计该括号对应的反括号是否出现
            //key-value 判断符号是否输入正确
            //最开始 输入的是左括号 pairs.count(ch) 返回 0
            if(pairs.count(ch)){
                //stk.top()!=pairs[ch] 判断该符号与栈顶符号是否为一对
                if(stk.empty()||stk.top()!=pairs[ch]){
                    return false;
                }
                stk.pop();
            }else{
                //没出现，入栈
                stk.push(ch);
            }
        }
        return stk.empty();
    }
    
};
// @lc code=end

知识点

• ​ 栈的一系列操作

  //创建符号栈
     	stack<char> stk;
  //栈判空
  	stk.empty();
  //出栈入栈
  	stk.pop();
  	stk.push(ch);
  

• ​ 哈希表的创建与操作

  //创建哈希表
  unordered_map<char, char> pairs = {
              {')', '('},
              {']', '['},
              {'}', '{'}
          };
  //哈希表查询
  //pairs.count(ch) 统计该括号对应的反括号是否出现
  //key-value 判断符号是否输入正确
  //最开始 输入的是左括号 pairs.count(ch) 返回 0
  	pairs.count(ch)//查到了就返回1 查不到就返回0
  
  //取值  pairs[key] = value
          pairs[ch]