首页 > 试题广场 >

有效的括号字符串

[编程题]有效的括号字符串
  • 热度指数:1816 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:
  1. 任何左括号 ( 必须有相应的右括号 )。
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )。
  4. * 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
  5. 一个空字符串也被视为有效字符串。
示例1

输入

"()"

输出

true
示例2

输入

"(*)"

输出

true
示例3

输入

"(*))"

输出

true

备注:
字符串大小将在 [1,100] 范围内。


function checkValidString( s ) {
    const arrStack = []
    for (let i = 0; i < s.length; i++) {
        let anyVal = s[i]
        if (anyVal === "*") arrStack.push("*")
        if (anyVal === "(") arrStack.push("(")
        if (anyVal === ")") {
            if (arrStack.length === 0) return false
            let numStarIndex = -1
            for (let j = arrStack.length - 1; j > -1; j--) {
                if (arrStack[j] === "(") {
                    arrStack.splice(j, 1)
                    break
                }
                if (arrStack[j] === "*" && numStarIndex === -1) numStarIndex = j
            }
            if (numStarIndex !== -1) arrStack.splice(numStarIndex, 1)
        }
    }
    let numTmp = Math.floor(arrStack.length / 2)
    for (let i = 0; i < numTmp; i++) {
        let anyLeft = arrStack[i]
        let anyRight = arrStack[arrStack.length - i - 1]
        if (anyLeft === "(" && anyRight === "*") {
            arrStack[i] = "*"
        }
        if (anyLeft === "*" && anyRight !== ")") {
            arrStack[arrStack.length - i - 1] = "*"
        }
    }
    if (arrStack.length !== 0) {
        return !(arrStack.indexOf("(") !== -1 || arrStack.indexOf(")") !== -1);
    }
    return true
}

发表于 2021-03-10 12:02:39 回复(0)