当前位置：首页 > article >正文

LeetCode热题100-有效的括号【JavaScript讲解】

article 2025/1/16 6:14:28

题目：

在这里插入图片描述

题解：

本题是「邻项消除」问题，我们遇到这类问题的时候可以用栈来解决它。
邻项消除是一种在字符串处理或数据结构中，通过删除相邻且满足特定条件（如相等或特定关系）的元素来简化或转换数据的操作‌。
这里我们来举例说明，例如s = “([])”
我们创建一个空栈stk来存储左括号
从左到右开始遍历
s[0] = ( ，这是一个左括号，左括号的我们都入栈处理
s[1] = [ ，同理入栈
s[2] = ] ，这是一个右括号，当我们遇到右括号的时候，就和栈顶的左括号做匹配，如果是匹配成功，那么就组成一队并弹出栈顶，否则括号类型不匹配。这里我们发现此处的 ] 和栈顶的 [ 相匹配，弹出栈顶。
s[3] = ) ，这是一个右括号，同理和栈顶做匹配，发现与栈顶的 ( 匹配成功，弹出栈顶继续向右遍历。
直到遍历结束，s的长度为0 且栈为null。

代码：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length % 2 !== 0){
        return false;
    }
    let stk = [];
    let mp ={'(':')','[':']','{':'}'};
    for(let ch of s){
        if(mp.hasOwnProperty(ch)){
            stk.push(ch);
        }else{
            if(stk.length === 0){
                return false;
            }
            let top = stk.pop();
            if(mp[top] !== ch){
                return false;
            }
        }
    }
    return stk.length === 0
};