20. 有效的括号

TIP

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

有效字符串需满足：

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

输入："()"
输出: true

解答

自己的答案

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    s = s.replace(/\s*/g,"");
    if(s.length%2 !== 0) return false;
    let result = []
    let right = [')','}',']'],ableArr=['()','[]','{}']
    let arr = s.split('')
    for(let i=0;i<arr.length;i++) {
        if(right.indexOf(arr[i]) > -1) {
            if(ableArr.indexOf(`${result[result.length-1]}${arr[i]}`) === -1) {
                return false;
            } else {
                result = result.slice(0,-1) // result.pop()
            }
        } else {
            result.push(arr[i])
        }
    }
    if(result.length===0) {
        return true
    } else {
        return false
    }
};

• 利用对象存储，复杂度均为O(n)

var isValid = function(s) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = []
    for(let i = 0; i < s.length ; i++) {
        if(map[s[i]]) {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
};