678. 有效的括号字符串｜刷题打卡

一、题目描述：

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

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

示例 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的关系，还需要考虑特殊情况的存在。