有效的括号

难度:简单

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

有效字符串需满足:

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

示例:

示例 1:

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

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

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

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

输入: "{[]}"
输出: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路分析:
实现方法一:
找到最内层的括号对,消去,重复此过程,若存在无法消去的字符则说明字符串无效

实现方法二:
遍历的时候遇到左括号存入数组,下次遇到的第一个右括号必须和数组中最后一个元素匹配,否则为无效字符串,匹配完成后从数组中删除此元素。若最终数组为空,表示括号已全部匹配完,字符串有效。

代码分析:

var isValid = function (s) {
    while (s.length) {
        var temp = s;
        s = s.replace('()', '');
        s = s.replace('[]', '');
        s = s.replace('{}', '');
        if (s == temp) return false
    }
    return true;
};

var isValid = function (s) {
    var map = {
        "(": ")",
        "[": "]",
        "{": "}"
    }
    var leftArr = []
    for (var ch of s){
        if (ch in map) leftArr.push(ch); //为左括号时,顺序保存
        else { //为右括号时,与数组末位匹配
            if(ch != map[leftArr.pop()]) return false;
        }
    }
    return !leftArr.length //防止全部为左括号
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
最后更新时间: 10/14/2019, 1:41:30 PM