678. Valid Parenthesis String
678. Valid Parenthesis String
题目
Given a string s
containing only three types of characters: '('
, ')'
and '*'
, return true
if s
is valid.
The following rules define a valid string:
- Any left parenthesis
'('
must have a corresponding right parenthesis')'
. - Any right parenthesis
')'
must have a corresponding left parenthesis'('
. - Left parenthesis
'('
must go before the corresponding right parenthesis')'
. '*'
could be treated as a single right parenthesis')'
or a single left parenthesis'('
or an empty string""
.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "(*)"
Output: true
Example 3:
Input: s = "(*))"
Output: true
Constraints:
1 <= s.length <= 100
s[i]
is'('
,')'
or'*'
.
题目大意
给你一个只包含三种字符的字符串,支持的字符类型分别是 '('
、')'
和 '*'
。请你检验这个字符串是否为有效字符串,如果是有效字符串返回 true
。
有效字符串符合如下规则:
- 任何左括号
'('
必须有相应的右括号')'
。 - 任何右括号
')'
必须有相应的左括号'('
。 - 左括号
'('
必须在对应的右括号之前')'
。 '*'
可以被视为单个右括号')'
,或单个左括号'('
,或一个空字符串。- 一个空字符串也被视为有效字符串。
解题思路
括号匹配的问题可以用栈求解。
如果字符串中没有星号,则只需要一个栈存储左括号,从左到右遍历字符串的过程中检查括号是否匹配。
在有星号的情况下,需要两个栈分别存储左括号和星号。从左到右遍历字符串:
- 如果遇到左括号,则将当前下标存入左括号栈。
- 如果遇到星号,则将当前下标存入星号栈。
- 如果遇到右括号,则需要有一个左括号或星号进行匹配,由于星号也可以看成右括号或者空字符串,因此当前的右括号应优先和左括号匹配,没有左括号时再和星号匹配:
- 如果左括号栈不为空,则从左括号栈弹出栈顶元素;
- 如果左括号栈为空且星号栈不为空,则从星号栈弹出栈顶元素;
- 如果左括号栈和星号栈都为空,则没有字符可以和当前的右括号匹配,返回
false
。
遍历结束之后,左括号栈和星号栈可能还有元素。为了将每个左括号匹配,需要将星号看成右括号,且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时,每次从左括号栈和星号栈分别弹出栈顶元素,对应左括号下标和星号下标,如果左括号下标大于星号下标则返回 false
。
最终判断左括号栈是否为空。如果左括号栈为空,则左括号全部匹配完毕,剩下的星号都可以看成空字符串,此时 s
是有效的括号字符串,返回 true
。如果左括号栈不为空,则还有左括号无法匹配,此时 s
不是有效的括号字符串,返回 false
。
代码
/**
* @param {string} s
* @return {boolean}
*/
var checkValidString = function (s) {
let pt_stack = [];
let star_stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") pt_stack.push(i);
else if (s[i] === "*") star_stack.push(i);
else {
if (pt_stack.length) pt_stack.pop();
else if (star_stack.length) star_stack.pop();
else return false;
}
}
while (pt_stack.length && star_stack.length) {
if (pt_stack[pt_stack.length - 1] > star_stack[star_stack.length - 1]) {
return false;
}
pt_stack.pop();
star_stack.pop();
}
return pt_stack.length === 0;
};
相关题目
- [761. 特殊的二进制序列](https://leetcode.com/problems/special-binary-string)
- [2116. 判断一个括号字符串是否有效](https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid)