Leecode20. 有效的括号——Leecode大厂热题100道系列

墨蓝 2022-09-14 13:28 113阅读 0赞

## 我是小张同学，立志用最简洁的代码做最高效的表达 ##

--------------------

以下是我个人做的题解，每个题都尽量囊括了所有解法，并做到了最优解，欢迎大家收藏！留言！

## 传送门——>[**Leecode大厂热题100道系列题解**][Leecode_100] ##

--------------------

### 问题描述 ###

> 给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 s ，判断字符串是否有效。  
>   
> 有效字符串需满足：  
>   
> 左括号必须用相同类型的右括号闭合。  
> 左括号必须以正确的顺序闭合。

> 示例 1：  
> 输入：s = “()”  
> 输出：true  
>   
> 示例 2：  
> 输入：s = “()\[\]\{\}”  
> 输出：true  
>   
> 示例 3：  
> 输入：s = “(\]”  
> 输出：false  
>   
> 示例 4：  
> 输入：s = “(\[)\]”  
> 输出：false  
>   
> 示例 5：  
> 输入：s = “\{\[\]\}”  
> 输出：true

--------------------

### 核心思路 ###

采用栈匹配的模式

false有三种情况：

1.  左右括号匹配不一致
2.  左括号数量大于右括号数量
3.  左括号数量小于右括号数量

按以上三种情况依次判断即可。 可以采用hash表来进行匹配。

--------------------

class Solution {
        
    public:
        bool isValid(string s) {
        
            stack<char> sta;
            unordered_map<char, char>um;
            um['('] = ')';  um['['] = ']'; um['{'] = '}';
    
            for(auto i : s) {
        
                if(i == '(' || i == '[' || i == '{') {
        
                    sta.push(i);
                } else {
        
                    // 匹配不上 或 左括号数量小于右括号数量
                    if(sta.empty() || um[sta.top()] != i) {
        
                        return false;
                    }
                    else {
        
                        sta.pop();
                    }
                }
            }
            // 左括号数量是否大于右括号数量
            return sta.empty() ? true : false;
        }
    };

[Leecode_100]: https://zhanglong.blog.csdn.net/article/details/120545161