【CodeTop】20. 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

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

示例 3：

输入：s = "(]"
输出：false
1
2

思路

使用数组实现栈，遍历字符串当遇到{、[、( 时入栈，遇到}、]、)判断栈顶符号是否与之匹配，匹配弹出栈否则返回false，遍历完成后判断数组长度是否为0

var isValid = function (str) {
    const stack = [];
    for (const s of str) {
        if (s === '{' || s === '[' || s === '(') {
            stack.push(s);
        } else if (s === '}' || s === ']' || s === ')') {
            if (isMatch(stack[stack.length - 1], s)) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
}

function isMatch(left, right) {
    if (left === '{' && right === '}') return true;
    if (left === '[' && right === ']') return true;
    if (left === '(' && right === ')') return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22