算法练习25：有效的括号(leetcode 20)

题目

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

有效字符串需满足：

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

示例
输入：s = "()"
输出：true
输入：s = "{[]}"
输出：true
输入：s = "(]"
输出：false

栈

1. 遍历字符串，如果为左括号，就入栈；
2. 如果遇到一个右括号了，那么如果是有效括号，它一定和之前最后一个左括号是匹配的，此时，将栈最后一个值最栈，查看是否为匹配括号，如果是，则继续，否则就不是有效括号
3. 利用这个原理，遍历完整个队列，如果此时栈为空，则代表是有效括号；如果栈中还有值，那么就是无效括号

比如：'{[]}'

• 第一步，'{'是左括号，入栈stack：['{']
• 第二步，'['是左括号，入栈stack：['{', '[']
• 第三步，']'是右括号，stack栈顶出栈, top = stack.pop() = '['，比对两个是一对括号，继续，此时stack：['{']
• 第四步，'}'是右括号，stack栈顶出栈, top = stack.pop() = '{'，比对两个是一对括号，此时stack：[]
• 此时，已经遍历完字符串了，查看stack为空，代表它是有效括号

var isValid = function(s) {
  // 有效括号长度一定是偶数，如果是奇数，就一定不是有效括号
  if(s.length % 2 == 1) return false;
  let stack = []
  let top = ''
  for(let i = 0; i < s.length; i++) {
      if(s[i] === '(' || s[i] === '{' || s[i] ==='[') {
          console.log(s[i])
          stack.push(s[i])
      }else {
          top = stack.pop()
          if( !((top == '(' && s[i] ==')') || (top == '{' && s[i] == '}') || (top == '[' && s[i] == ']')) ) {
              return false;
          }
      }
  }
  if(stack.length) {
    return false;
  }
  return true;
};

let res = isValid("()")
console.log(res)   // true

优化一下代码

上面那一长串判断，有点让人看不下去，使用对象保存括号对，采用key、value方式来比对；最后判断返回也可以简写

var isValid = function(s) {

  // 有效括号长度一定是偶数，如果是奇数，就一定不是有效括号
  if(s.length % 2 == 1) return false;
  let stack = []
  let top = ''
  // 保存括号的配对，根据右括号判断其左括号对不对
  let obj = {
      ')': '(',
      ']': '[',
      '}': '{'
  }
  for(let i = 0; i < s.length; i++) {
      if(s[i] === '(' || s[i] === '{' || s[i] ==='[') {
          stack.push(s[i])
      }else {
          top = stack.pop()
          // 使用对象key，value形式比对
          if(obj[s[i]] !== top) {
              return false;
          }
      }
  }
  // 简化下最后判断
  return !stack.length
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)