LeetCode[20]有效的括号

2020年05月26日Web前端、算法0

一天一道算法题系列，趁还刷的动，速度走起。

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"

输出: true

示例 2:

输入: "()[]{}"

输出: true

示例 3:

输入: "(]"

输出: false

示例 4:

输入: "([)]"

输出: false

示例 5:

输入: "{[]}"

输出: true

思路

由于对若干个符号进行匹配，所以用数组存放会比较好些，当我们遇到右侧类型的括号时，需要与前一个比较，此时，该数组最好是个栈类型的(js数组完美支持)。

由于比较时，利用 === 这种方式双比较太复杂，所以使用正反括号为正负数值的方式方便判断。

实现

/**
 * @param {string} 
 * @return {boolean}
 */
var isValid = function(s) {
    const len = s.length
    const map = {
        '(': -1,
        ')': 1,
        '{': -2,
        '}': 2,
        '[': -3,
        ']': 3,
        '': 0
    }
    const list = []
    let res = true

    for (let ind = 0; ind < len; ++ind) {
        if (['(', '{', '['].indexOf(s[ind]) > -1) {
            list.push(s[ind])
        } else {
            let prev = list.pop() || ''

            if (map[prev]+ map[s[ind]]) {
                // 匹配不上
                res = false
                break
            }
        }
    }

    if (list.length) {
        res = false
    }

    return res
};
【每天一道算法题】LeetCode算法

目录