LeetCode-20.有效的括号

haiweilian2021-03-05算法LeetCode

题目描述

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

有效字符串需满足：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

解法一之栈

使用栈记录左括号，循环时如果是左括号就入栈，如果是右括号就出栈，最后栈里面没有元素就是有效的

可以先判断下是不是偶数，如果不是那肯定是无效的。
然后可以创建一个栈，和一个左括号和右括号的映射表。
当遍历的时候，如果遇到左括号就入栈(push)一个字符；如果遇到右括号就出栈(pop)一个字符，并且取出这个字符对应的右括号判断和当前的右括号是否一致，不一致直接返回。
最后当遍历结束时，判断栈中还有没有字符。有则返回 false，没有返回 true。

代码实现

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 判断是否是偶数
  if (s.length % 2 !== 0) return false;

  // 创建一个栈，和左右括号对应的字典
  let stack = [];
  let obj = { "(": ")", "{": "}", "[": "]" };

  for (let i = 0; i < s.length; i++) {
    let k = s[i];
    if (k in obj) {
      // 如果是左括号，入栈。
      stack.push(k);
    } else {
      // 如果不是左括号，那么按理说应该开始闭合标签了。
      // 取出栈中的最后一个字符的右括号和当前字符对比，如果不匹配直接结束。
      if (obj[stack.pop()] !== k) {
        return false;
      }
    }
  }

  // 如果栈中没有字符，那么就是有效的
  return !stack.length;
};
// ===================================================================
// ========================== @test ==================================
// ===================================================================
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("([)]")); // false

LeetCode-20.有效的括号

题目描述

解法一之栈

ON THIS PAGE