20. 有效的括号｜刷题打卡-阿里云开发者社区

20. 有效的括号｜刷题打卡

2022-05-01 86

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：• 左括号必须用相同类型的右括号闭合。• 左括号必须以正确的顺序闭合。

一、题目描述：

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

有效字符串需满足：

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

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

提示：

1 <= s.length <= 10^4

s 仅由括号 '()[]{}' 组成

二、思路分析：

题目很简单，使用一个栈便可以解决。根据提示可知，字符串长度大于等于1，所以可以不考虑为0的情况。

考虑'('，'['，'{'这三种情况，符合要求时，应该将其压栈；
符合')'，'}'，']'这三种情况时，应该判断此时的栈顶是否于闭合的三个字符相匹配。

匹配。例如：栈顶为'('，当前字符为')'时，就应该将'('出栈
不匹配。直接不满足要求

例子：

s = "{[]}"

网络异常，图片无法展示

最后，根据栈是否为空进行返回判断。如果不符合匹配条件可直接返回false。

三、AC 代码：

function isValid(s: string): boolean {
  let stack = [];
  stack[0] = s[0];
  for (let i = 1; i < s.length; i++) {
    switch (s[i]) {
      case "(":
        stack.push("(");
        break;
      case "[":
        stack.push("[");
        break;
      case "{":
        stack.push("{");
        break;
      case ")":
        if (stack[stack.length - 1] === "(") {
          stack.pop();
        } else {
          return false;
        }
        break;
      case "]":
        if (stack[stack.length - 1] === "[") {
          stack.pop();
        } else {
          return false;
        }
        break;
      case "}":
        if (stack[stack.length - 1] === "{") {
          stack.pop();
        } else {
          return false;
        }
        break;
    }
  }
  return stack.length ? false : true;
};

四、总结：

利用栈解决字符串匹配问题只是其中一种解决方法，还可以使用对象的key、value来解决。

作者：ClyingDeng

链接：https://juejin.cn/post/6947973790496194573

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。