DT走过的路

描述

给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:

1.左括号'(‘必须有对应的右括号’)’

2.右括号’)’必须有对应的左括号'(‘

3.左括号必须在对应的右括号前面

4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符

5.空字符串也视为合法的括号字符串

数据范围:

1<=s.length<=1001<=s.lengt**h<=100

示例1

输入：

"()()"

返回值：

true

示例2

输入：

"((*)"

返回值：

true

示例3

输入：

"(*)"

返回值：

true

示例4

输入：

"(((*)"

返回值：

false

思路：

1. 由于*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符，所以单栈不能处理
2. 一个栈处理（，一个栈处理*，并记录下标
3. 星号的下标必须在左括号右边

function isValidString(s) {
    // write code here
    let leftStack = []; // 存左括号下标
    let starStack = []; // 存星号下标
    for (let i = 0; i < s.length; i++) {
        //入栈处理
        if(s[i]==='('){
            leftStack.push(i);
        }else if(s[i]==='*'){
            starStack.push(i);
        }else if(s[i]===')'){
            if(leftStack.length){
                leftStack.pop()
            }else if(starStack.length){
                starStack.pop()
            }else{
                // 无左括号、无星号匹配，直接false
                return false;
            }
        }
    }

    while(leftStack.length && starStack.length){
        const leftIdx = leftStack.pop();
        const startIdx = starStack.pop();
        if(leftIdx>startIdx) return false;
    }
    return !leftStack.length;
    
}