128-data_structure-2-stack~20有效的括号

概述

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

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

测试

输入:s = "()"
输出:true

输入:s = "()[]{}"
输出:true

输入:s = "(]"
输出:false

输入:s = "([)]"
输出:false

输入:s = "{[]}"
输出:true

解题思路

{[()]}

1、需要遍历所有字符串

2、遇到左括号先略过,遇到右括号开始匹配,匹配的是最后遇到的左括号

3、后进先出模式,左括号逐一入栈,若遇到右括号,则取栈顶元素左括号

解题步骤

1、新建一个栈
2、扫描字符串,遇左括号入栈,遇到和栈顶括号类型匹配的右括号就出栈,类型不匹配直接判定为不合法
3、最后栈空了就合法,否则不合法

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2 === 1) {
    return false
  }
  const stack = []
  for (const value of s) {
    if (value === '(' || value === '[' || value === '{') {
      stack.push(value)
    }else {
      const stack_top = stack[stack.length-1]
      if (
        (stack_top === '(' && value === ')') ||
        (stack_top === '[' && value === ']') ||
        (stack_top === '{' && value === '}')
      ) {
        stack.pop()
      }else {
        return false
      }
    }
  }
  return stack.length === 0
};
var isValid = function(s) {
  const length = s.length
  if (length % 2 === 1) {
    return false
  }
  const stack = []
  let index = -1
  while (++index < length) {
    const value = s[index]
    if (value === '(' || value === '[' || value === '{') {
      stack.push(value)
    }else {
      const stack_top = stack[stack.length-1]
      if (
        (stack_top === '(' && value === ')') ||
        (stack_top === '[' && value === ']') ||
        (stack_top === '{' && value === '}')
      ) {
        stack.pop()
      }else {
        return false
      }
    }
  }  
  return stack.length === 0
};

复杂度

  • 时间复杂度:O(n),其中 n是字符串 s 的长度。
  • 空间复杂度:O(n)

总结

1、栈适合解决对称类问题

2、先分析不合理情况,若存在,则提前返回

推荐阅读

代码随想录