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

吐槽君 分类:javascript

本文正在参与掘金团队号上线活动,点击 查看详情

一、题目描述:

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

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

示例 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 = (*))
image.png

image.png
最后,stack栈length为0,说明符合匹配要求。

步骤二:

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

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

例子2:

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

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

image.png

image.png

三、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的关系,还需要考虑特殊情况的存在。

回复

我来回复
  • 暂无回复内容