力扣--有效的括号

有效的括号

题目描述

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]
            
    
    
上一篇:巨型星座try7_3(stk串口可见性报告)


下一篇:456. 132 Pattern(Leetcode每日一题-2021.03.24)--抄答案