2. 有效的括号（678）

一、题目内容 简单中等困难

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

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

示例1：

输入: "()" 输出: True

示例2：

输入: "(*)" 输出: True

示例3：

输入: "(*))" 输出: True

注意:

1. 字符串大小将在 [1，100] 范围内。

   二、解题思路

   贪心的思想，做这道题。
   从左到右遍历字符串，遍历过程中，未匹配的左括号的数量可能出现如下的变化：

• 如果遇到左括号，则未匹配的左括号数量加 1
• 如果遇到右括号，则需要有一个左括号和右括号匹配，匹配成功后，未匹配的左括号数量减 1
• 如果遇到星号，由于星号可以看成左括号、右括号、空字符，因此未匹配的左括号数量可能加 1，减 1，或不变

基于上述结论，可以在遍历的过程中维护未匹配的左括号数量可能的最大值、最小值

• 如果遇到左括号，则将最大值，最小值都加 1
• 如果遇到右括号，则将最大值、最小值都减 1
• 如果遇到星号，则将最大值加 1，最小值减 1

注意，未匹配的左括号数量必须非负，因此最大值小于 0 时，说明没有左括号可以跟右括号匹配了，返回 false

当最小值为 0 时，不应将最小值继续减小，以确保最小值非负。
遍历结束时，所有的左括号都应和右括号匹配，因此只有当最小值为 0 时，字符串 s 才是有效的括号字符串。

三、具体代码

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function (s) {
  let min = max = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c === '(') {
      min += 1;
      max += 1;
    } else if (c === ')') {
      min = min === 0 ? 0 : min - 1;
      max -= 1;
      if (max < 0) return false;
    } else if (c === '*') {
      min = min === 0 ? 0 : min - 1;
      max += 1;
    }
  }
  return min === 0;
};
/**
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */

四、其他解法

动态规划

栈