20. 有效的括号

[GpingFeng]

20. 有效的括号

可以根据栈来解决，根据先进后出的原则，当匹配到是闭合括号时，出栈的总应该是和它相匹配的，否则就是非法的

var isValid = function(s) {
    let stack = [];
    for(let i of s) {
        let target = stack[stack.length - 1];
        if ((i === ')' && target === '(') || 
        (i === ']' && target === '[') ||
        ((i === '}' && target === '{'))) {
            stack.pop();
            continue;
        }
        stack.push(i);
    }
    return stack.length === 0;
}

复杂度分析

• 时间复杂度——O(n)
• 空间复杂度——O(n)

[GpingFeng]

栈 + Map

跟上面一样，只是多加一个 map 结构存储

var isValid = function(s) {
    // 由题目可以发掘我们可以利用栈的先进后出特性来解决这个问题
    // 定义一个常量记录括号的信息
    if (s.length % 2 !== 0) return false;
    const mapBrackets = {
      '(': -1,
      ')': 1,
      '{': -2,
      '}': 2,
      '[': -3,
      ']': 3
    }
    let stack = []
    for (let i = 0; i < s.length; i++) {
      let cur = mapBrackets[s[i]]
      if (cur < 0) {
        stack.push(cur)
      } else {
        if (cur + stack.pop() !== 0) {
          return false
        }
      }
    }
    if (stack.length > 0) {
      return false
    }
    return true
}