首页 > 试题广场 >

合法的括号字符串

[编程题]合法的括号字符串
  • 热度指数:11988 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个字符串s,字符串s只包含以下三种字符: (,*,),请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:
1.左括号'('必须有对应的右括号')'
2.右括号')'必须有对应的左括号'('
3.左括号必须在对应的右括号前面
4.*可以视为单个左括号,也可以视为单个右括号,或者视为一个空字符
5.空字符串也视为合法的括号字符串

数据范围:

示例1

输入

"()()"

输出

true
示例2

输入

"((*)"

输出

true
示例3

输入

"(*)"

输出

true
示例4

输入

"(((*)"

输出

false
根据能成对的括号不断消除看最后是否只剩星号来判断是否是合法的括号字符串
function isValidString( s ) {
    // write code here
    // 根据星号数量和左右括号数量最少的数量的和和左右括号数量最多的数量作比较来淘汰不符合的字符
    let leftCount = s.match(/\(/g)?s.match(/\(/g).length:0;
    let rightCount = s.match(/\)/g)?s.match(/\)/g).length:0;
    let xingCount = s.match(/\*/g)?s.match(/\*/g).length:0;
    if(xingCount+Math.min(leftCount,rightCount) < Math.max(leftCount,rightCount)){
        return false
    }
    else{
         // 定义三个匹配模式匹配可以成对的括号
        let pattern1 = /\((\**)\)/;//中间的括号用于捕获
        let pattern2 = /\(\*/;//注意,这里不加g,是为了每次都能从头匹配
        let pattern3 = /\*\)/;
        while(pattern1.test(s)){
            s = s.replace(/\((\**)\)/g,'$1');//$1是捕获的第一个数据
        }
        while(pattern2.test(s)){
            s = s.replace(/\(\*/g,'');
        }
        while(pattern3.test(s)){
            s = s.replace(/\*\)/g,'');
        }
        if(/^\**$/.test(s)){
            return true
        }else{
            return false
        }
    }
}

    
发表于 2022-09-14 02:54:57 回复(0)