有效的括号

题目

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

思路分析

判断括号的有效性，可以使用 「 栈 」这一数据结构来解决。

1. 判断括号的有效性的一个前提条件是字符串的长度一定为偶数，如果字符串长度为奇数，说明括号是无效的，我们直接返回 false，省去后续遍历判断过程。
2. 为了快速判断括号的类型，我们使用字典(也称映射)这一数据结构存储每一种括号。字典的键为左括号，值为右括号。另外使用数组来模拟栈结构。
3. 对给定的字符串进行遍历，当我们遇到一个左括号时，我们期望在后续的遍历中，会有一个相同类型的右括号将其闭合，因此我们可以先将这个左括号放入栈中。当我们遇到一个右括号时，我们需要一个相同类型的左括号闭合，此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串是无效的，返回 false。
4. 在遍历结束后，如果栈中没有元素，说明字符串中的所有左括号都有与之对应的右括号将其闭合，也就是我们要判断的字符串是有效的，返回 true，否则返回 false。

代码实现

使用ES6的Map存储括号

/**
*@param {string} s
*@return {boolean}
*/
var isValid = function(s) {
    const len = s.length;
  // 判断字符串长度是否为偶数，如果为奇数，则字符串无效，返回false
  if (len % 2 === 1) return false;
  // 使用数组模拟栈结构
  const stack = [];
  // 使用 Map 存储括号
  const map = new Map([['(', ')'], ['[', ']'], ['{', '}']]);
  for (let i = 0; i < len; i++) {
    const str = s[i];
      if (map.has(str)) {
      // 是左括号，则入栈
        stack.push(str)
    } else {
        if (str != map.get(stack.pop())) {
        // 此时遇到的是右括号，出栈的左括号与右括号不是同类型的括号，或者栈中没有左括号，
        // 说明字符串是无效的，返回 false，结束后续循环
        return false
      }
    }
  }
  // 遍历结束后，如果栈为空，说明字符串是有效的，返回 true，否则返回 false
  return !stack.length
}

使用Object存储括号

/**
*@param {string} s
*@return {boolean}
*/
var isValid = function(s) {
    const len = s.length;
  // 判断字符串长度是否为偶数，如果为奇数，则字符串无效，返回false
  if (len % 2 === 1) return false;
  // 使用数组模拟栈结构
  const stack = [];
  // 使用对象(字典)存储括号
  const map = {
    '(': ')',
    '[': ']',
    '{': '}'
  }
  for (let i = 0; i < s.length; i++) {
    const str = s[i];
    if (str in map) {
      // 是左括号，则入栈
      stack.push(str)
    } else {
      if (str != map[stack.pop()]) {
        // 此时遇到的是右括号，出栈的左括号与右括号不是同类型的括号，或者栈中没有左括号，
        // 说明字符串是无效的，返回 false，结束后续循环
        return false
      }
    }
  }
  // 遍历结束后，如果栈为空，说明字符串是有效的，返回 true，否则返回 false
  return !stack.length
}