首页 > 试题广场 >

有效括号序列

[编程题]有效括号序列
  • 热度指数：370987 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给出一个仅包含字符仅由括号字符 \texttt{`['}、\texttt{`]'}、\texttt{`('}、\texttt{`)'}、\texttt{`\{'}、\texttt{`\}'} 的括号序列字符串 s（0 \leqq |s| \leqq 10^4），你需要判断给出的括号序列字符串 s 是否是有效的括号序列。

\hspace{15pt}有效括号序列的定义如下：
\hspace{23pt}\bullet\,空序列是有效括号序列；
\hspace{23pt}\bullet\,如果 A 是有效括号序列，则 \texttt{(A)}、\texttt{[A]} 和 \texttt{{A}} 都是有效括号序列；
\hspace{23pt}\bullet\,如果 A 和 B 都是有效括号序列，则它们的拼接 AB 也是有效括号序列。

\hspace{15pt}如果括号序列字符串 s 是有效的括号序列，返回一个布尔值 \texttt{true}；否则返回一个布尔值 \texttt{false}。
示例1

输入

"["

输出

false
示例2

输入

"[]"

输出

true

备注:
\hspace{15pt}要求：空间复杂度 ，时间复杂度 。
算法知识视频讲解
添加回答
JavaScript Node
Explorer丶头像 Explorer丶 
function isValid( s ) {
    // write code here
    let obj = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        if (Object.keys(obj).includes(s[i])) {
            stack.push(s[i]);
        }
        else {
            if (s[i] !== obj[stack.pop()]) {
                return false 
            }
        }
    }
    return !stack.length;


}
module.exports = {
    isValid : isValid
};

编辑于 2024-03-25 22:56:27 回复(0)
JavaScript Node
矜持的微笑头像 矜持的微笑
function isValid(s) {
    if (s.length % 2 !== 0) return false;
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            stack.unshift(")");
        } else if (s[i] === "[") {
            stack.unshift("]");
        } else if (s[i] === "{") {
            stack.unshift("}");
        } else if (stack.length === 0 || stack.shift() !== s[i]) {
            return false;
        }
    }
    return stack.length === 0;
}
编辑于 2024-01-27 16:19:36 回复(0)
JavaScript Node
牛客710667568号头像 牛客710667568号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return bool布尔型
 */

function isValid(s) {
    // write code here
    let stack = [];
    let flag = true;
    let i = 0;
    while (i < s.length) {
        if (s[i] == "{" || s[i] == "(" || s[i] == "[") {
            stack.push(s[i]);
        } else {
            switch (s[i]) {
                case ")":
                    if (stack[stack.length - 1] == "(") {
                        stack.pop();
                        break;
                    } else {
                        flag = false;
                    }
                case "}":
                    if (stack[stack.length - 1] == "{") {
                        stack.pop();
                        break;
                    } else {
                        flag = false;
                    }
                case "]":
                    if (stack[stack.length - 1] == "[") {
                        stack.pop();
                        break;
                    } else {
                        flag = false;
                    }
            }
        }
        i++;
    }
    return flag && stack.length == 0
}
module.exports = {
    isValid: isValid,
};

发表于 2023-09-06 18:52:34 回复(0)
JavaScript Node
rick_Han头像 rick_Han 
function isValid(s) {
    // write code here
    let len = s.length
    for (let i = 0; i < len / 2; i++){
        s = s.replace("{}", "").replace("()", "").replace("[]", "");
        console.log(s)
    }
    
    return s === ''
}

发表于 2023-04-11 09:18:34 回复(2)
JavaScript Node
牛客549040466号头像 牛客549040466号 
/**
  * 
  * @param s string字符串 
  * @return bool布尔型
  * （{[(    )]}）
  */
function isValid( s ) {
    // write code here
    let stack=[];
    const len=s.length;
const map = new Map();
map.set('{','}');
map.set('[',']');
map.set('(',')');

for(let i=0;i<len;i++){
if(map.has(s[i])){
    stack.push(map.get(s[i]))
}else if(s[i]===stack[stack.length-1]){
     stack.pop(map.get(s[i]));
}else{
    return false;
}


}
if(stack.length)return false
return true
}
module.exports = {
    isValid : isValid
};

发表于 2023-03-27 17:02:25 回复(0)
JavaScript Node
牛客931461884号头像 牛客931461884号 
let strL = ["(", "{", "["];
let strR = [")", "}", "]"];
let arr=[];
function isValid(s) {
    // write code here
    let i=0;
    while(i<s.length){
        console.log(strL.indexOf(s[i]))
        if(strL.indexOf(s[i])!=-1){
            arr.push(s[i]);
        }else if(strL.indexOf(arr[arr.length-1])==strR.indexOf(s[i])){
            arr.pop()
            console.log(arr.length);
        }else{
            return false;
        }
    i++;
    }
    return arr.length==0?true:false;
}
module.exports = {
    isValid: isValid,
};

发表于 2023-03-26 17:40:25 回复(0)
JavaScript Node
w布响丸辣头像 w布响丸辣 
function isValid( str ) {
    let stack = [];
    for(let s of str){
        if(stack.length){
            if(isMatch(stack[stack.length-1],s)){
                stack.pop()
            }else{
                stack.push(s)
            }
        }else{
            stack.push(s)
        }
    }
    function isMatch(left,right){
        if(left==='('&&right===')'||left==='{'&&right==='}'||left==='['&&right===']'){
            return true
        }
        return false;
    }
    return !stack.length;
}

发表于 2022-08-24 23:58:45 回复(0)
JavaScript Node
summer_swilder头像 summer_swilder
function isValid( s ) {
    const map = {
        '(': ')',
        '{': '}',
        '[': ']'
    };
    let stack = [];
    for (let i of s) {
        if (['(', '[', '{'].includes(i)) {
            stack.push(i);
        } else if (map[stack.pop()] !== i) {
            return false;
        }
    }
    return !stack.length;
}
发表于 2022-04-26 22:36:50 回复(0)
JavaScript Node
FoRtCurious头像 FoRtCurious
function isValid( s ) {
    // write code here
    if (s.length === 0 || s.length %2 === 1) return false;
    
    let reg = /\(\)|\[\]|\{\}/g
    while (s.match(reg)) {
        s = s.replace(reg, '')
    }
    return s.length === 0
}


发表于 2021-12-11 16:29:13 回复(0)
JavaScript Node
乱不能头像 乱不能
/**
  * 
  * @param s string字符串 
  * @return bool布尔型
  */
function isValid( s ) {
    let result = []
    for(let i in [...s]){
       if(s[i] == '['){
           result.push(']')
       }
       else if(s[i] == '{'){
           result.push('}')
       }
       else if(s[i] == '('){
           result.push(')')
       }
       else if(result.length == 0 || result.pop() != s[i]){
           return false
       }
    }
    return result.length == 0

}
module.exports = {
    isValid : isValid
};
发表于 2021-09-30 00:20:11 回复(0)
提交观点

问题信息

字符串 栈
难度：
11条回答 39550浏览

热门推荐

通过挑战的用户

查看代码

相关试题

有效括号序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号