一、题目描述

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

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

二、思路分析

"()"
"()[]{}"
"{[]}"

先观察给定的有效字符串示例中的输入，将他们按照顺序来处理，在某一刻他们都是对称的。

根据栈的后进先出原则，一组数据的入栈和出栈顺序刚好是对称的。

所以我们可以利用栈来依次入栈字符，当遇到一对相匹配的字符就将他们出栈。

当然这里可以省去右括号的入栈、出栈操作，遇到与栈顶字符相匹配的右括号时，直接将栈顶的左括号出栈即可。

每配对成功一对括号，都将这对括号出栈，可以确保栈顶的括号总是下一个需要被匹配的左括号。

最后，若字符串全都匹配，栈一定为空，若栈不为空，则输入的不是有效字符串。

三、AC 代码

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function(s) {
    // 用一个 map 来维护左括号和右括号的对应关系,方便比对
    const map = {
    "(": ")",
    "[": "]",
    "{": "}"
    };
  // 空字符串直接返回 true
  if (!s) {
    return true;
  }
  //用栈来存左括号
  const stack = [];
  // 遍历字符串
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    // 若是左括号则入栈
    if (["(", "{","["].indexOf(ch) !=-1) {
        stack.push(ch);
    }
    // 若是右括号则判断是否和栈顶的左括号相配对
    else {
      // 若栈不为空，且栈顶的左括号和当前字符不匹配，返回false
      if (!stack.length || map[stack.pop()] !== ch) {
        return false;
      }
    }
  }
  //若栈为空则说明全都匹配
  return !stack.length;
};

四、总结

当遇到对称性的问题时，可以尝试着从栈入手，来解决问题。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情