LeetCode 20 有效的括号

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

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

1. 暴力法

巧妙

var isValid = function(s) {
    let len;
    // 循环结束条件，len 的长度与 s.length不相等，两者都在变，不相等意味着存在成对的括号被替换成空，一旦替换成空，那么就继续
    while(len !== s.length) {
        len = s.length;
        s = s.replace(/()|[]|{}/g, '')
    }
    // 如果括号匹配，那么最终会被替换成''，长度变为 0
    return !s.length
}

2. 利用栈顶

思路：利用栈。遇到左括号，一律推入栈中。遇到右括号，将栈顶部元素拿出，如果不匹配则返回 false，如果匹配则继续循环。

var isValid = function(s) {
    let arr = [];
    // 提高性能
    if(s.length % 2 !== 0) return false;
    for(let i = 0; i < s.length;i++) {
        switch(s[i]) {
            case '(': {
                arr.push(s[i]);
                break;
            }
            case '[': {
                arr.push(s[i]);
                break;
            }
            case '{': {
                arr.push(s[i]);
                break;
            }
            case ')': {
                if(arr.pop() !== '(') return false;
                break;
            }
            case ']': {
                if(arr.pop() !== '[') return false;
                break;
            }
            case '}': {
                if(arr.pop() !== '{') return false;
                break;
            }
        }
    }
    return !arr.length;
};

3. 边遍历，边匹配。

换一种思路，可以边遍历边匹配。也就是遍历的时候遇到左括号存入数组，下次遇到的第一个右括号必须和数组中最后一个元素匹配，否则为无效字符串，匹配完成后从数组中删除此元素。若最终数组为空，表示括号已全部匹配完，字符串有效。

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 //防止全部为左括号
};