20. Valid Parentheses

source: https://leetcode.com/problems/valid-parentheses/

Question

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

思路

看到括号，一开始联想到了22题，其实22题中也要判断()的有效性，但这题的判断明显要复杂很多，因为有多种括号类型。

一开始用排除法的方式，写出所有无效的情况，很难写对。

用栈的方式就清晰明了很多:

• 对于闭口，上一个必然是自己的合口（因为其他括号对都被pop了）

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    if (s.length % 2 === 1) return false;
    const stack = [];
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
    for (let char of s) {
        if (map[char]) {
            const last = stack.pop();
            if (last !== map[char]) return false;
        } else {
            stack.push(char);
        }
    }
    return !stack.length;
};

总结

对于括号有效性问题，要优先想到用栈的数据结构。