[20] 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

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

示例 1:

输入: "()"

输出: true

示例 2:

输入: "()[]{}"

输出: true

示例 3:

输入: "(]"

输出: false

示例 4:

输入: "([)]"

输出: false

示例 5:

输入: "{[]}"

输出: true

这道题是一道经典的符号匹配题，涉及到成对抵消的题我们应当首先考虑使用栈来解决。在这道题里有三对符号匹配且有前后关系（即左括号在右括号之前才合法），因此我们再划分符号为左括号和右括号两部分。当然，如果你认定题目不会给你除了这几个符号之外的字符，也可以用左括号与非左括号划分，这样可以减少两个集合的使用，直接用一个map即可。

之后进行遍历，若是左括号，则直接入栈。若是右括号，将之与栈顶元素比较看是否成对，如果不成对或者栈中没有符号则直接返回false，否则将栈顶取出，进入下一次循环。

这里还有一个剪枝的小技巧：如果字符串长度为奇数，则不可能是一个有效的字符串，返回false。

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false;
  const stack = [];
  const leftMap: Record<string, string> = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  for (let i = 0; i < s.length; i++) {
    // 若为左括号，则入栈
    if (leftMap[s[i]]) {
      stack.push(s[i]);
    } else {
      // 若为右括号，则与栈顶元素匹配看是否为一对
      const temp = stack.pop();
      if (leftMap[temp] !== s[i]) return false;
    }
  }
  if (stack.length !== 0) return false;
  return true;
}