Description

题解

知识点：栈

算法步骤：

1. 用一个map记录每一个括号的对应关系，再用map记录下右括号到左括号的映射关系
2. 遇到左括号就入栈，遇到右括号就出栈
3. 然后判断出栈的左括号是否和右括号匹配：方式就是通过右括号拿回左括号，然后判断是否相等。不相等直接返回false。
4. 最后判断栈是否为空，如果为空就是true，否则就是false

function isValid(s: string): boolean {
  const map = new Map<string, string>(Object.entries({
    ')': '(',
    ']': '[',
    '}': '{',
  }));
  const stack: string[] = [];

  // 维护右括号到左括号的映射关系 + 从左往右看字符碰到左括号入栈，碰到右括号就让左括号出栈然后匹配映射关系
  for (let i = 0; i < s.length; i++) {
    // 如果是右括号
    if (map.has(s[i])) {
      const p = stack.pop()!;
      if (map.get(s[i]) !== p) {
        return false;
      }
    }
    else {
      // 否则是左括号，入栈
      stack.push(s[i]);
    }
  }

  // 如果栈中还有字符，说明没匹配完全，否则s为有效括号
  return stack.length === 0;
};
Copy