内容

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

有效字符串需满足：

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

思路

其实就是入栈出栈的问题，如果是左括号，那么入栈，如果是右括号，那么栈顶匹配的元素出栈。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    var array = s.split('');
    var input = [];
    var output = [];

    for (var i = 0; i < array.length; i++) {
        if (/\(|\[|\{/.test(array[i])) {
            input.push(array[i]);
        } else {
            if (array[i] == ')' && input[input.length - 1] == '(') {
                input.pop()
            } else
            if (array[i] == ']' && input[input.length - 1] == '[') {
                input.pop()
            } else
            if (array[i] == '}' && input[input.length - 1] == '{') {
                input.pop()
            } else {
                return false;
            }
        }
    }
    return input.length == 0;
};

回到目录