题解 | #有效括号序列#

okkjoo-leetcodeHot-byJs带你用 JS 刷高频面试算法题~还有各种常用、常考手写, 最近还加了自己实现的流行库的mini版本合集仓库：okkjoo-leetcodeHot-byJs欢迎 star⭐

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

解题思路

括号问题，常考的就是栈的运用与操作了~

遍历字符串s，分情况讨论：

• 拿到左括号：压入栈中
• 拿到右括号，分类讨论：栈不为空：栈顶为对应的左括号：取出栈顶，继续遍历栈顶不是对应的左括号，return false栈为空: 直接return false

遍历完之后，如果栈中还有括号，就说明有左括号没有右括号来与之配对，return false

扩展：

也可以通过设置计数器变量存储左右括号出现次数来进行判断

pps：只有一种括号类型的时候才可以使用计数器这个方法:（（）），如果不止一种括号，可能就会有些样例过不了，所以这个方法是无效的，例如这种示例4([)]'，没有以正确的顺序闭合。

⭐：

• 栈的操作
• JS中的数组中的push、popAPI 就可以模拟栈

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stk = [] //数组模拟栈
    const mp = new Map()////对应括号映射
    mp['(']=')'
    mp['{']='}'
    mp['[']=']'
    for(let c of s){
        //拿到左括号
        // if(['(','[','{'].indexOf(c) != -1){
        if(c in mp){
            stk.push(c)
        }else {
            const top = stk.pop()
            if(c !== mp[top]) return false //栈顶不是对应的左括号或者为undefined
        }
    }
    if(stk.length)return false
    return true//一切都恰当
};

okkjoo-leetcodeHot-byJs带你用 JS 刷高频面试算法题~还有各种常用、常考手写, 最近还加了自己实现的流行库的mini版本合集仓库：okkjoo-leetcodeHot-byJs欢迎 star⭐