[路飞]_leetcode-20-有效的括号

「这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

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

有效字符串需满足：

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

示例 1：

输入： s = "()"
输出： true
复制代码

示例 2：

输入： s = "()[]{}"
输出： true
复制代码

示例 3：

输入： s = "(]"
输出： false
复制代码

示例 4：

输入： s = "([)]"
输出： false
复制代码

示例 5：

输入： s = "{[]}"
输出： true
复制代码

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

本题要我们判断输入字符串中的括号是否都一一对应

那么我们就需要在遇到右括号的时候，判断它前面是否是与之对应的左括号

如果不是，返回 false

但是这里有一个问题，就是当前括号对比成功后，如何不妨碍后续的括号对比，也就是每一个后面的字符，如何找到前面与之对应的字符的位置

这里我们可以用栈来维护所有的左括号，当遇到左括号，入栈

当遇到右括号的时候，此时栈顶字符就是与之对应的字符，判断两个字符是否是对应括号，如果不是，返回 false,否则将栈顶元素弹出，这样就保证了后续有括号遍历到的时候，栈顶元素还是与之对应的字符

解题思路如下：

1. 创建一个栈，用来后续存储所有的左括号
2. 为了不针对每一种右括号做一次判断逻辑代码编写，创建一个 obj 维护括号之间的对应关系
3. 遍历字符串，如果当前字符为左括号，将该字符入栈
4. 如果当前字符为右括号，判断栈顶元素是否是与之对应的左括号，如果不是，返回 false,否则将栈顶元素弹出，方便后续对比
5. 如果字符串顺利遍历完成，说明所有的右括号都恰好有与之对应的做括号
6. 最后判断栈是否为空，如果不为空，说明有多余的左括号，返回 false,否则说明左右括号完全一一对应，返回 true

代码如下：

var isValid = function(s) {
  // 创建栈存储左括号
  const stack = [],
  // 利用obj维护对应关系
  obj = {
    ')':'(',
    ']':'[',
    '}':'{'
  }
  // 遍历字符串
  for(let i = 0;i<s.length;i++){
    switch(s[i]){
      // 如果为左括号，入栈
      case '(':
      case '[':
      case '{':
        stack.push(s[i])
      break;
      // 如果为右括号，判断当前栈顶字符是否是其对应左括号，如果不是，返回 false
      case ')':
      case ']':
      case '}':
        if(stack.length === 0 || stack.pop() !== obj[s[i]]) return false;
      break;
    }
  }
  // 代码来到这里遍历过程中所有右括号都匹配到了对应的左括号
  // 此时如果栈为不为空，说明左括号存在多余情况，反之说明输入字符串有效
  return stack.length === 0
};
复制代码

至此，我们就完成了leetcode-20-有效的括号

如有任何问题或建议，欢迎留言讨论！