20.有效括号

https://leetcode-cn.com/problems/valid-parentheses/

• 20.有效括号

  • 题目描述

  • 方法 1：栈

    • 思路

    • 代码

    • 复杂度分析

  • 方法 2：递归

    • 思路

    • 代码

    • 复杂度分析

  • 方法 3：正则

    • 思路

    • 代码

    • 复杂度分析

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：栈

思路

• 遇到左括号就入栈。

• 遇到右括号就从栈中弹出一个元素，判断两者是否是匹配的一对括号。

代码

JavaScript Code

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const dict = {
        '}': '{',
        ')': '(',
        ']': '[',
    };
    const stack = [];

    for (let c of s) {
        if (c in dict) {
            if (stack.pop() !== dict[c]) {
                return false;
            }
        } else {
            stack.push(c);
        }
    }
    return stack.length === 0;
};

复杂度分析

• 时间复杂度：$O(n)$，n 为字符串的长度。

• 空间复杂度：$O(n)$，n 为字符串的长度。

方法 2：递归

思路

产品经理法(⓿_⓿) 假设我们现在已经有了一个 isValid 方法，可以验证一个字符串 s 是否由有效括号组成。

那么子问题是什么？

如果 s 的第一个字符是左括号的话，那我们应该可以找到它对应右括号的下标 index，如果找不到说明就不是有效括号啦。

如果找到了，那么现在问题就变成了：

• (0, index) 中间这段字符串是否包含有效括号？

• (index, s.length) 这段字符串是否包含有效括号？

开括号表示不包括边界

大问题和小问题的关系是什么？

显然必须两个小问题的结果都是 true 才行啦，也就是：

isValid(s) = isValid(1, index - 1) && isValid(index + 1, s.length)

递归出口在哪里？

• 如果字符串第一个字符不是左括号，return false

• 如果字符串为空，return true

• 还有一个，如果字符串长度是奇数的话，我们也可以提前 return false。

关于如何找到对应的右括号下标

用一个 counter 来记录当前遇到的括号，比如，我们要找的是 '(' 的对应右括号 ')'，那么在遍历字符串时：

• 遇到 '(' 时 counter++

• 遇到 ')' 时 counter--

• 当 counter === 0 时说明我们找到了

• 如果遍历结束后 counter > 0 说明找不到匹配的右括号

代码

JavaScript Code

const dict = {
    '(': ')',
    '{': '}',
    '[': ']',
};

const matchClose = (s, start, end, open, close) => {
    let count = 0;
    for (let i = start; i <= end; i++) {
        if (s[i] === open) count++;
        if (s[i] === close) count--;
        if (count === 0) return i;
    }
    return -1;
};

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function (s) {
    if (!s) return true;
    if (s.length % 2 === 1) return false;
    if (!(s[0] in dict)) return false;

    const closeIndex = matchClose(s, 0, s.length - 1, s[0], dict[s[0]]);
    if (closeIndex === -1) return false;
    return (
        isValid(s.slice(1, closeIndex)) &&
        isValid(s.slice(closeIndex + 1, s.length))
    );
};

复杂度分析

• 时间复杂度：TODO

• 空间复杂度：$O(n)$，n 为字符串的长度，调用栈的最大深度是 $n/2$。

方法 3：正则

思路

不断地把 () {} [] 替换成空字符，直到：

• s 变成了空字符，那么结果就是 true，或者，

• s 长度不为空，但是 s 中已经没有 ()，{} 或者 [] 括号对了，那么结果就是 false。

代码

JavaScript Code

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function (s) {
    const reg = /\[\]|\(\)|\{\}/;
    while (reg.test(s)) {
        s = s.replace(reg, '');
    }
    return s.length === 0;
};

复杂度分析

• 时间复杂度：$O(n)$，n 为字符串的长度。最坏的情况下，每次循环只能替换一对括号，比如 "(((((())))))"，需要循环 n/2 次。

• 空间复杂度：$O(1)$。