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 = (*))
最后,stack栈length为0,说明符合匹配要求。
步骤二:
匹配多余(
。字符串遍历完,可能出现stack和star栈存在长度。
此时,我们就还需要对匹配之后的stack和star进行判断。我们可以将不符合情况的找出来,最后符合的就直接返回true。不符合的:
- star长度小于star,说明
*
不够去填补(
,直接不符合情况; - star长度大于等于stack:说明大体可以满足
(
配对。- 特殊情况:
*(
,此时我们应该调整方法,将s中的下标分配到两个栈中。在此情况下,判断两个栈顶元素值,当star.pop() < stack.pop()
时是不符合条件的。
- 特殊情况:
例子2:
s = (*())(*((**()
经过步骤一匹配后,stack与star均存在长度不为零的情况,并且star长度大于stack。
此时,需要判断各自栈顶元素值。在两个栈都存在的情况下循环,两栈的栈顶相比较,star.pop() < stack.pop()
时直接返回false。stack长度为空时停止循环。
三、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的关系,还需要考虑特殊情况的存在。