20. 有效的括号

我的提交：

function isValid(s) {
    if (!s || (s.length % 2 !== 0)) return false;
    const closeTag = ['}', ')', ']'];
    const keyMap = {
        '{': '}',
        '}': '{',
        '(': ')',
        ')': '(',
        '[': ']',
        ']': '['
    };
    const sArr = s.split('');
    const tmp = [];
    while (sArr.length) {
        const source = tmp.length && tmp[tmp.length - 1] || '';
        const target = sArr.shift();
        const isCloseTag = closeTag.includes(target);
        if (!tmp.length && isCloseTag) {
            return false;
        }
        if (source === keyMap[target]) {
            tmp.pop();
        } else if (!isCloseTag) {
            tmp.push(target);
        } else {
            return false;
        }
    }
    return tmp.length === 0 ? true : false;
};

执行用时: 56 ms
内存消耗: 41.3 MB

一开始理解错了，以为只要成对成对出现即可，但实际上有时候并不是有效的，如：([)]，虽然相应符号都成对，但它并不是有效的，所以并不是简单的把对应的符号消掉即可。
但既然强调有效，其实就有规律，假设我们用一个栈来存放，那么有如下规律：

1. 只有起始符号能进数组
2. 当遇到的是结束符号时，想要其有效，其对应的起始符号一定就在栈底，匹配则出栈消掉

所以实现了上面的代码。

后来看了官方的代码后，学习优化了一下，得到如下实现：

function isValid(s) {
    if (!s || (s.length % 2 !== 0)) return false;
    const tagMap = new Map([
        ['}', '{'],
        [')', '('],
        [']', '[']
    ]);
    const tmp = [];
    for (let i of s) {
        if (tagMap.has(i)) {
            if (!tmp.length || tagMap.get(i) !== tmp[tmp.length-1]) {
                return false;
            }
            tmp.pop();
        } else {
            tmp.push(i);
        }
    }
    return tmp.length === 0 ? true : false;
};

优雅了许多，不需要把所有字符都做映射，只需要把结束字符作 key 做个映射即可。

1. 只要字符是存在 map 里的，证明是个结束字符
2. 如果不是结束字符，那只能是起始字符，起始字符只能出现在结束字符前面，所以先推进栈
3. 如果是结束字符，则需要看一下是否跟栈底的字符匹配，匹配的话就弹出栈
4. 这里使用了逆向思维，当是结束字符时，只要栈是空的，或者与栈底的字符不匹配，则直接结束了，因为结束字符不能入栈，入了就不是有效字符了