• 定义左括号key 右括号value 的map 和 一个stack
    • 遍历字符串每次将左括号推入stack中，遇到右括号则从stack取出，通过map进行比对
    • 如果比对失败则返回false
    1. /**
    2.  * @param {string} s
    3.  * @return {boolean}
    4.  */
    5. var isValid = function(s) {
    6.     const stack = []
    7.     const stringMap = {
    8.         '(':')',
    9.         '[':']',
    10.         '{':'}'
    11.     }
    13.     for(let key of s){
    14.        if(stringMap[key]){
    15.            stack.push(stringMap[key])
    16.        }else{
    17.            if(stack.pop() !== key) return false
    18.        }
    19.     }
    21.     return !stack.length
    22. };

    时间复杂度:

    • 对字符串进行了一次遍历所以是 O(n)

    **
    空间复杂度:

    • 需要一个stack来存放左括号 ，所以是 O(n)