每天一道leetcode(Day 35)

20. 有效的括号

题目描述

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

有效字符串需满足：

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

示例

示例 1:

输入: "()"
输出: true

示例  2:

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

示例  3:

输入: "(]"
输出: false

示例  4:

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

示例  5:

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

解题思路

利用栈结构:将字符串中的字符依次入栈，遍历字符依次判断：

• 首先判断该元素是否是 { 、 ( 、 [ ，如果是的话则直接入栈，如果该字符为 } 、 ) 、 ] 中的一种且如果该字符串有效，则该元素应该与栈顶匹配，例如栈中元素有 ({， 如果继续遍历到的元素为 ), 那么当前元素序列为 ({) 是不可能有效的，所以此时与栈顶元素匹配失败，则直接返回 false ，字符串无效
• 当遍历完成时，所有已匹配的字符都已匹配出栈，如果此时栈为空，则字符串有效，如果栈不为空，说明字符串中还有未匹配的字符，字符串无效

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const map = {
    "{": "}",
    "[": "]",
    "(": ")",
  };
  let stack = [];
  for (let item of s) {
    if (map[item]) {
      stack.push(item);
    } else {
      if (item !== map[stack.pop()]) return false;
    }
  }
  return stack.length === 0;
};

参考

20. 有效的括号