LeetCode20. 有效的括号(面试高频题)｜刷题打卡

女爷i 2022-11-05 12:48 138阅读 0赞

# 一、题目描述 #

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串 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;
    };

# 四、总结 #

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