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

一、题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 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来解决。