LeetCode

20. 有效的括号

栈结构

栈 => 后进先出

题解

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 1. 如果字符串length为奇数, 肯定不匹配
  if (s.length % 2 === 1) return false
  // 2. 栈结构处理，左括号，入栈，右括号，出栈; 数组的最后一个作为栈顶
  const stack = []
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char)
    } else {
      // 出栈，并和栈顶对比, 如果匹配，就出栈
      const top = stack[stack.length - 1]
      if (
        (top === '(' && char === ')') ||
        (top === '[' && char === ']') ||
        (top === '{' && char === '}')
      ) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  // 最后，栈应该为空，如果不为空，说明有未闭合的括号
  return stack.length === 0
}

代码简化，用map结构定义左右括号的关系

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 1. 如果字符串length为奇数, 肯定不匹配
  if (s.length % 2 === 1) return false
  // 2. 栈结构处理，左括号，入栈，右括号，出栈; 数组的最后一个作为栈顶
  const stack = []
  // 3. map定义左右括号对应关系
  const map = {
    '(': ')',
    '{': '}',
    '[': ']'
  }
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    if (map[char]) {
      // 左括号，入栈
      stack.push(char)
    } else {
      // 如果是右括号，检查是否与栈顶的左括号匹配
      // 匹配直接出栈
      const top = stack.pop()
      if (char !== map[top]) {
        return false
      }
    }
  }
  // 最后，栈应该为空，如果不为空，说明有未闭合的左括号 Error
  return stack.length === 0
}