最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 678. 有效的括号字符串|刷题打卡

    正文概述 掘金(ClyingDeng)   2021-04-07   89

    一、题目描述:

    给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:

    • 任何左括号 ( 必须有相应的右括号 )
    • 任何右括号 ) 必须有相应的左括号
    • 左括号 ( 必须在对应的右括号之前 )
    • 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
    • 一个空字符串也被视为有效字符串。

    示例 1:

    输入:s = ()
    输出:true

    示例 2:

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

    示例 3:

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

    提示:

    字符串大小将在 [1,100] 范围内

    二、思路分析:

    题目在20的基础上增加了一点变化,引入*,可以代替()或空。

    步骤一:

    我们可以引入两个栈stack和star,分别保存(*,通过遍历字符串,将)与两个栈的相匹配。

    • stack栈有,先匹配stack栈,stack存在,就pop()即可;
    • stack栈无,就匹配star,star执行pop();
    • 两者均无,直接返回false。

    例子1:

    s = (*)) 678. 有效的括号字符串|刷题打卡

    678. 有效的括号字符串|刷题打卡 最后,stack栈length为0,说明符合匹配要求。

    步骤二:

    匹配多余(。字符串遍历完,可能出现stack和star栈存在长度。
    此时,我们就还需要对匹配之后的stack和star进行判断。我们可以将不符合情况的找出来,最后符合的就直接返回true。不符合的:

    • star长度小于star,说明*不够去填补(,直接不符合情况;
    • star长度大于等于stack:说明大体可以满足(配对。
      • 特殊情况:*(,此时我们应该调整方法,将s中的下标分配到两个栈中。在此情况下,判断两个栈顶元素值,当star.pop() < stack.pop()时是不符合条件的。

    例子2:

    s = (*())(*((**()

    经过步骤一匹配后,stack与star均存在长度不为零的情况,并且star长度大于stack。 678. 有效的括号字符串|刷题打卡 此时,需要判断各自栈顶元素值。在两个栈都存在的情况下循环,两栈的栈顶相比较,star.pop() < stack.pop()时直接返回false。stack长度为空时停止循环。

    678. 有效的括号字符串|刷题打卡

    678. 有效的括号字符串|刷题打卡

    三、AC 代码:

    function checkValidString(s: string): boolean {
        let stack = [];
        let star = [];
        for (let i = 0; i < s.length; i++) {
            switch (s[i]) {
                case "(":
                    stack.push(i);
                    break;
                case "*":
                    star.push(i);
                    break;
                case ")":
                    if (stack.length) {
                        stack.pop();
                    } else if (star.length) {
                        star.pop();
                    } else {
                        return false;
                    }
                    break;
            }
        }
        if (star.length >= stack.length) {
            while (star.length && stack.length) {
                if (star.pop() < stack.pop()) return false;
            }
        } else {
            return false;
        }
        return true;
    };
    

    四、总结:

    在上一题的基础上进行扩展,同样是使用栈来分别保存(*,然后进行匹配,主要是需要找到两个栈和s的关系,还需要考虑特殊情况的存在。


    起源地 » 678. 有效的括号字符串|刷题打卡

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元