20.有效的括号（题）

题目地址

初始思路

// https://leetcode.cn/problems/valid-parentheses/description/

/***
示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([])"
输出：true
 */

/**
 * @param {string} s
 * @return {boolean}
 *
 * 思路：用栈实现
 * 得是偶数    得包含开始括号  开始括号的数量 === 结束括号的数量
 * 1. 遍历字符串，遇到 （ { [ 入栈
 * 2. 当前栈顶的元素遇到与之匹配的括号时，出栈
 * 3. 最后栈为空则返回true
 */
var isValid = function (s) {
  if (!s) return false;
  // 不包含开始括号，直接返回false
  if (!s.includes("(") && !s.includes("{") && !s.includes("[")) {
    return false;
  }
  // 不是偶数，直接返回false
  if (s.length % 2 !== 0) {
    return false;
  }
  // 开始括号的数量 !== 结束括号的数量，直接返回false
  let startNum = s
    .split("")
    .filter((item) => item === "(" || item === "{" || item === "[");
  let endNum = s
    .split("")
    .filter((item) => item === ")" || item === "}" || item === "]");
  if (startNum.length !== endNum.length) {
    return false;
  }
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    const current = s[i];
    if (current === "(" || current === "{" || current === "[") {
      stack.push(current);
    } else {
      const stackEnd = stack[stack.length - 1];
      if (
        (stackEnd === "(" && current === ")") ||
        (stackEnd === "{" && current === "}") ||
        (stackEnd === "[" && current === "]")
      ) {
        stack.pop();
      }
    }
  }

  return !stack.length;
};

/**
 * 时间复杂度分析：O(n)
 */

console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([])")); // true
console.log(isValid("([)]")); // false
console.log(isValid("([}}])")); // false

看解析后的思路

/**
 * @description: 第二种方法   栈  +   哈希表
 * @param {*} s
 * @returns {*}
 */
/**
 * 思路：
 * 1. 当 current } 他的前一个必须是 {  所以可以用map来存储
 * 2. 当 current 是开始括号 入栈
 * 3. 当是结束括号的时候，需要跟当前栈的最后一个进行比对
 */
const isValid2 = function (s) {
  // 不是偶数，直接返回false
  if (s.length % 2 !== 0) {
    return false;
  }
  // 开始括号的数量 !== 结束括号的数量，直接返回false
  let startNum = s
    .split("")
    .filter((item) => ["(", "{", "["].includes(item)).length;
  let endNum = s
    .split("")
    .filter((item) => [")", "}", "]"].includes(item)).length;
  if (startNum !== endNum) {
    return false;
  }
  const map = new Map([
    [")", "("],
    ["}", "{"],
    ["]", "["],
  ]);
  const stack = [];

  for (let item of s) {
    // 如果当前是结束括号
    if (map.has(item)) {
      // 当前的前一个是对应的开始括号  出栈
      if (!stack.length) return false;

      if (stack[stack.length - 1] === map.get(item)) {
        stack.pop();
      }
    } else {
      // 如果当前是开始括号 入栈
      stack.push(item);
    }
  }
  return !stack.length;
};

console.log(isValid2("()")); // true
console.log(isValid2("()[]{}")); // true
console.log(isValid2("(]")); // false
console.log(isValid2("([])")); // true
console.log(isValid2("([)]")); // false
console.log(isValid2("([}}])")); // false   特殊
console.log(isValid2("[")); // false        特殊