有效的括号｜刷题打卡-一一网

本文正在参与掘金团队号上线活动，点击查看大厂春招职位

题目描述

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

有效字符串需满足：

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

输入：s = "()[]{}"
输出：true

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true
复制代码

思路分析

仔细看下题目，左括号必须以正确的顺序闭合 意味着字符串里，起码有一对符合是连在一起的，类似() {} []，这样才算正确顺序的闭合，如果左右符合都不匹配，则无法正确闭合，类似(}这种情况的出现。

这就想到了一种替换的方式来处理，将字符串里成对连在一起的字符移除，一遍遍的去移除，直到所有的成对字符串消失。可以采用replace方法替换成空字符串处理，{[()]}，先替换()，剩下{[]}，接着剩下{}，最后，最后结果是空字符串的就满足了情况。

代码

通过indexOf来判断是否包含相应的字符串，然后一遍遍去循环替换。

const isValid = function (s) {
    while (s.indexOf("()") > -1 || s.indexOf("[]") > -1 || s.indexOf("{}") > -1) {
        if (s.indexOf("()") > -1) {
            s = s.replaceAll("()", "");
        }
        if (s.indexOf("{}") > -1) {
            s = s.replaceAll("{}", "");
        }
        if (s.indexOf("[]") > -1) {
            s = s.replaceAll("[]", "");
        }
    }
    return s.length === 0;
};

复制代码

从实现的层面来看，这段代码没有任何问题，但是从运行速度上来看，确实不咋地。

还有一种方式，通过遍历字符串，每遇到左符号装进临时数组stack，每遇到一个右符号，即有一个左符号满足匹配，stack里最后的左符号先闭合。有点类似栈的后进先出，后进的左符号先被匹配了。

const isValid = function (s) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = []
    for (let i = 0; i < s.length; i++) {
        if (map[s[i]]) {
            //遇到左符合，装进数组
            stack.push(s[i])
        } else if (s[i] !== map[stack.pop()]) {
            //遇到右符合，跟stack最后的左符号不匹配即false，匹配的话，stack.pop移除最后的左符号
            return false
        }
    }
    return stack.length === 0;
};
复制代码