算法(41)-有效的括号

栈与队列

 2024/03/16 

题目(easy)

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思路

匹配类的题目非常适合用栈。

出问题的场景：

最后栈不为空，说明左括号多了
中途不匹配，说明左右括号不一致
栈空了还没匹配完，说明右括号多了

const isValid = (s) => {
    const stack = [];
    const map = {
        "(":")",
        "{":"}",
        "[":"]",
    };
    for(const x of s) {
        if (x in map) {
            stack.push(map[x]);
            continue;
        }
        if (stack.pop() !== x) {
            return false;
        }
    }
    return !stack.length;
}

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/16/2024-03-16-%E7%AE%97%E6%B3%95(41)-%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7/

发表日期：March 16th 2024, 11:13:13 pm

更新日期：March 17th 2024, 12:12:55 am

Next Post

算法(42)-删除字符串中的所有相邻重复项
Previous Post

算法(40)-用队列实现栈

CATALOG

1. 题目(easy)
2. 思路