Loveyless的学习笔记

Appearance

Return to top
On this page

题目

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

题解

栈类题的开篇之作 我以前并没有栈的思想 所以这道题首先就是明确为什么可以用栈的思想来做

左括号依次入栈 右括号和栈顶对比 巧妙的利用了栈的特性来做题

ts
function isValid(s: string): boolean {
  if (!s.length) return false;
  if (s.length % 2 !== 0) return false;

  const pairs = new Map();
  pairs.set("{", "}");
  pairs.set("[", "]");
  pairs.set("(", ")");

  let stack = [];

  for (let c of s) {
    //如果表中有左括号
    if (pairs.has(c)) {
      //放入栈中
      stack.push(c);
    } else if (pairs.get(stack.pop()) !== c) {
      //如果栈顶括号不等于右括号 则返回错误
      return false;
    }
  }

  //遍历完栈后 栈是否为空
  return stack.length === 0;
}