题目内容

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

有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

()[]{}，([{}])，((){[]})，这些都是true。

第一遍看完题没有清晰的思路。看完示例后想的是，应该主要有两种有效的类别，一是像这样的([{}])嵌套对称，二是像这样的{}[]紧挨对称。

但同时对于这种形式{()[{}]}的是否符合对称要求也抱有疑问，便先处理前两种类别的。

处理完发现就是在有疑问的那类case里卡住了。

错误解答

var isValid = function(s) {
    if(s.length % 2 === 1 || s.length === 1) {
        return false
    }
    let map = {
        ')' : '(',
        ']' : '[',
        '}' : '{'
    }
    if (map[s[1]] === s[0]) {
        // 紧挨对称
        for (let i = 0; i < s.length - 1;) {
            if (map[s[i + 1]] === s[i] ) {
                // 加2是因为紧挨对称是以组的形式出现
                i = i + 2
            } else {
                return false
            }
        }
        return true
    } else if (s[0] === map[s[s.length - 1]]){
        // 嵌套对称
        for(let i = 0; i < s.length / 2;) {
            // 判断与对称点位置的元素是否匹配
            if (s[i] === map[s[s.length - 1 - i]]) {
                i ++ 
            } else {
                return false
            }
        }
        return true
    }
    return false
};

官方解法

上午的思路走不下去之后，也没想到更好的法子，只好去看官方解法。看完拍手叫好，思路很清晰，实现所需的代码也很简单。

实现完后一看，应该刷题以来最好看的击败率，但这个击败率其实是不稳定的。其中原因也求证过LeetCode内部人员，原话是：

服务器跑的时候根据负载，时间会有差别，测试集越少越明显。

官方解法在网站从开始到最后分析了很多，简单来说就是：用栈来存储目前遇到的左括号，一旦遇到与已有左括号匹配的右括号，就将左括号出栈。自然理想的情况是循环完一遍，栈里面没有剩下元素。

反之，如果有，则意味着存在不匹配的括号。

var isValid = function(s) {
    if(s.length % 2 === 1 || s.length === 1) {
        return false
    }
    let arr = []
    let map = {
        '(' : ')',
        '[' : ']',
        '{' : '}'
    }
    for (let i = 0; i < s.length;) {
        if (s[i] in map) {
            arr.push(s[i])
        } else if (s[i] === map[arr[arr.length - 1]]){
            arr.pop()
        }
        i++
    }
    return arr.length > 0 ? false : true
};

思路清奇的解法

这个解法是中国站rhinoc同学提供的，看完必须拍大腿。

这个解法是针对所有给到的测试用例至少都会有一组紧挨对称的括号(如[{}])。那每一次循环将紧挨对称的括号去除掉，到最后理想的情况就如官方解法一样，没有剩下的括号元素。

这个解法的代码也很简洁，但可能因为replace的原因，时间复杂度和空间复杂度效果都不是很好。

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;
}