[算法] - 有效的括号

[renjie-run]

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

思路 这里可以利用栈的思路来辅助解决，首先判断栈中是否存在与当前括号对应的闭合括号，不存在直接入栈，存在的话进一步判断栈中最后一个括号与当前括号对应的闭合括号是否一致，一致则说明这两个括号形成有效闭合，则进行出栈操作，否则说明改组括号字符串无效，结束循环。循环结束判断栈是否为空，为空则表明有效，否则无效。

这里字符串长度为奇数的话也是无效的。

如果栈的长度超过括号字符串长度的一半时，此时匹配是无法完成，也可以认定为是无效的。

解法一

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  let sLength = s.length;
  if (sLength % 2 == 1) {
    return false;
  }
  let halfSLength = sLength / 2;
  let bracketsMap = {
    ')': '(',
    '}': '{',
    ']': '['
  }
  let stack = [];
  for(let i = 0; i < sLength; i++) {
    let bracket = s[i];
    let matchedBracket = bracketsMap[bracket];
    if (stack.indexOf(matchedBracket) > -1) {
      let closestBracket = stack[stack.length - 1];
      if (closestBracket !== matchedBracket) {
        break;
      } else {
        stack.pop();
      }
    } else {
      stack.push(curr);
    }
    if (stack.length > halfSLength) {
      break;
    }
  }
  if (stack.length === 0) {
    return true;
  }
  return false;
};