通过字典的方式实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (n)

    1. function isValid(s) {
    2.   if (s.length % 2 === 1) {
    3.       return false;
    4.   }
    6.   const stack = [];
    7.   const map = new Map();
    9.   map.set('(', ')');
    10.   map.set('{', '}');
    11.   map.set('[', ']');
    13.   for (let i = 0; i < s.length; i++) {
    14.       const item = s[i];
    16.       if (map.has(item)) {
    17.           stack.push(item);
    18.       } else {
    19.           const top = stack[stack.length - 1];
    21.           if (map.get(top) === item) {
    22.               stack.pop();
    23.           } else {
    24.               return false;
    25.           }
    26.       }
    27.   }
    29.   return stack.length === 0;
    30. }

上方代码只有一层 for 循环所以时间复杂度是 O (n)。同理空间复杂度是 O (n) 因为开辟的空间 stack 的长度是受 n 影响的，而 map 的长度是固定的只有3个，所以忽略不计。