678. 有效的括号字符串

🟠   🔖  栈 贪心 字符串 动态规划  🔗 力扣 LeetCode

题目

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 。

有效字符串符合如下规则：

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

解题思路

括号匹配的问题可以用栈求解。

如果字符串中没有星号，则只需要一个栈存储左括号，从左到右遍历字符串的过程中检查括号是否匹配。

在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串：

• 如果遇到左括号，则将当前下标存入左括号栈。
• 如果遇到星号，则将当前下标存入星号栈。
• 如果遇到右括号，则需要有一个左括号或星号进行匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时再和星号匹配：
  1. 如果左括号栈不为空，则从左括号栈弹出栈顶元素；
  2. 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
  3. 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 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	特殊的二进制序列		递归 字符串
2116	判断一个括号字符串是否有效		栈 贪心 字符串