678. Valid Parenthesis String

678. Valid Parenthesis Stringopen in new window

🟠 🔖 栈 贪心 字符串 动态规划 🔗 LeetCodeopen in new window

题目

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;
};

678. Valid Parenthesis String

# 678. Valid Parenthesis Stringopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

678. Valid Parenthesis Stringopen in new window

题目

题目大意

解题思路

代码

相关题目