C++力扣题目20--有效的括号

2023-12-25 13:09:36

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

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

示例?2:

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

示例?3:

输入:s = "(]"
输出:falses

思路:

由于栈结构的特殊性,非常适合做对称匹配类的题目。

首先要弄清楚,字符串里的括号不匹配有几种情况。

一些同学,在面试中看到这种题目上来就开始写代码,然后就越写越乱。

建议在写代码之前要分析好有哪几种不匹配的情况,如果不在动手之前分析好,写出的代码也会有很多问题。

先来分析一下 这里有三种不匹配的情况,

  1. 第一种情况,字符串里左方向的括号多余了 ,所以不匹配。?

    括号匹配1

  2. 第二种情况,括号没有多余,但是 括号的类型没有匹配上。?

    括号匹配2

  3. 第三种情况,字符串里右方向的括号多余了,所以不匹配。?

    括号匹配3

我们的代码只要覆盖了这三种不匹配的情况,就不会出问题,可以看出 动手之前分析好题目的重要性。

动画如下:

20.有效括号

第一种情况:已经遍历完了字符串,但是栈不为空,说明有相应的左括号没有右括号来匹配,所以return false

第二种情况:遍历字符串匹配的过程中,发现栈里没有要匹配的字符。所以return false

第三种情况:遍历字符串匹配的过程中,栈已经为空了,没有匹配的字符了,说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢,就是字符串遍历完之后,栈是空的,就说明全都匹配了。

分析完之后,代码其实就比较好写了,

但还有一些技巧,在匹配左括号的时候,右括号先入栈,就只需要比较当前元素和栈顶相不相等就可以了,比左括号先入栈代码实现要简单的多了!

实现C++代码如下:

class Solution {
public:
    bool isValid(string s) {
        stack<char>sta;
        if (s.size() % 2 != 0) { return false; }//如果s的长度为奇数,一定不匹配
        for (int i = 0; i < s.size(); i++)
        {                                               
            if (s[i] == '(') { //如果是左括号,转换一下插入右括号
            sta.push(')');      //方便后面插入右括号进行相等比较进行抵消
            continue; 
            }
            if (s[i] == '[') { 
                sta.push(']'); 
                continue;
            }
            if (s[i] == '{') { 
                sta.push('}'); 
                continue;
            }
            if (sta.empty()||sta.top() !=s[i]) { return false; }//出现第三种情况,右括号多余
            if (sta.top() == s[i]) { //如果插入的括号与栈顶括号匹配就出栈
                sta.pop();
            }
            
        }
        return sta.empty();
    }
};

文章来源:https://blog.csdn.net/weixin_47675625/article/details/135193072
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。