算法图解：如何判断括号是否有效？

- 日理万妓 2023-10-05 11:50 66阅读 0赞

![format_png][]

作者 | 王磊

来源 | Java中文社群（ID：javacn666）

转载请联系授权（微信ID：GG\_Stone）

今天要讲的这道题是 bilibili 今年的笔试真题，也是一道关于栈的经典面试题。

经过前面文章的学习，我想很多朋友已经看出来了，**我接下来要写的是一个关于「算法图解」的系列文章**，中间可能会穿插少量的其他类型的文章，但「算法和数据结构」会是我今年文章输出的重点内容。

我在写这个算法系列的时候会注意两个问题：

*  **保证算法的解题思路大家都能看懂，因此我会以图片的形式进行思路讲解，这样更直观、更易于理解**；
 *  **在介绍完一个知识点之后，会进行大量的练习，以巩固所学的内容**，比如当我讲完「栈」结构之后，我会围绕着「栈」做一系列的经典面试题练习。

> 学习算法最关键的是掌握解题的思路，只要思路对了，编写代码只是时间的问题。

我们先来回顾一下往期关于「栈」的内容：

*  [《动图演示：手撸堆栈的两种实现方法！》][Link 1]
 *  [《JDK 竟然是这样实现栈的？》][JDK]
 *  [《链表反转的两种实现方法，后一种击败了100%的用户！》][100]
 *  [《算法图解：如何找出栈中的最小值？》][Link 2]

那么接下来，我们就进入今天的正式内容...

#### 题目 ####

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

有效字符串需满足：

*  左括号必须用相同类型的右括号闭合。
 *  左括号必须以正确的顺序闭合。
 *  注意空字符串可被认为是有效字符串。

**示例 1:**

> 输入: "()"
> 
> 输出: true

**示例 2:**

> 输入: "()\[\]\{\}"
> 
> 输出: true

**示例 3:**

> 输入: "(\]"
> 
> 输出: false

**示例 4:**

> 输入: "(\[)\]" 输出: false

**示例 5:**

> 输入: "\{\[\]\}"
> 
> 输出: true

> LeetCode 地址：https://leetcode-cn.com/problems/valid-parentheses

#### 解题思路 ####

这道题考察的是就是验证括号的对称性，比如“(\[\{\}\])”这种字符串就是正确的，应该返回 true，而“(\[\{\})\]”这种字符串就是错误的，应该返回 false。

从上面的题目可以看出，括号总共分为三类：小括号、中括号和大括号，那么**我们可以利用栈先进后出的特性，将所有左边的括号（“(”、“\[”、“\{”）先入栈，然后再碰到右括号时，让它与栈顶的元素进行匹配，比如当遇到“)”时，如果栈顶是“(”，则说明匹配成功，栈顶元素出栈再继续字符串循环的流程，如果匹配错误就直接返回 false。**

假设我们要匹配字符串“((\[\]))”是否合法？那么执行流程就是这样的。

首先遇到左边括号，先入栈：

![format_png 1][]

接下来又是左边括号，继续入栈：

![format_png 2][]

然后又是左边括号，继续入栈：

![format_png 3][]

接下来是右边括号，与栈顶元素匹配，“\[\]”为一对合法的括号，匹配成功栈顶元素出栈：

![format_png 4][]

接下来又是右边括号，与栈顶元素匹配，“()”为一对合法的括号，匹配成功栈顶元素出栈：

![format_png 5][]

接下来又是右边括号，与栈顶元素匹配，“()”为一对合法的括号，匹配成功栈顶元素出栈：

![format_png 6][]

当字符串循环结束并且栈为空栈时，则证明此字符串的括号匹配合法，最终的效果如下图所示：

![format_png 7][]

那么接下来我们就用代码来实现一下整个过程...

#### 实现代码一 ####

public boolean isValid(String s) {
        int slen = s.length(); // 括号的长度
        if (slen % 2 == 1) { // 括号不是成对出现直接返回 false
            return false;
        }
        // 把所有对比的括号存入 map，对比时用
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        // 定义栈，用于存取括号（辅助比较）
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < slen; i++) { // 循环所有字符
            char c = s.charAt(i);
            if (map.containsKey(c)) { // 为右边的括号，如 ')'、'}' 等
                if (stack.isEmpty() || stack.peek() != map.get(c)) { // 栈为空或括号不匹配
                    return false;
                }
                stack.pop(); // 是一对括号，执行出栈（消除左右括号）
            } else { // 左边括号，直接入栈
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

我们在 LeetCode 中提交一下代码，执行结果如下：

![format_png 8][]

##### 代码解析 #####

以上代码的 `map` 集合是用于定义括号的匹配规则，比如“)”对应的匹配值是“(”，“\]”的匹配值是“\[”等，然后我们再去循环待验证的字符串，遇到左括号直接入栈，遇到右括号让它与栈顶元素匹配，等到整个字符串循环结束，如果栈为空则说明字符串的括号合法。

##### 复杂度分析 #####

时间复杂度：O(n)，遍历了一遍整个字符串。空间复杂度：O(n)。

#### 实现代码二 ####

除了使用栈之外，我们还可以使用借助 Java 中的 `replace` 方法来实现，我们可以循环的消除字符串中的括号，比如将“()”或“\[\]”或“\{\}”循环得替换为空，最后在执行完成之后如果字符串为空，则说明字符串中的括号是合法的，具体实现代码如下：

public boolean isValid(String s) {
            int len;
            do {
                len = s.length();
                // 消除成双成对的符号
                s = s.replace("()", "").replace("[]", "").
                        replace("{}", "");
            } while (len != s.length()); // 不能再进行替换了，replace 方法没有替换任何字符
            return s.length() == 0;
        }

我们在 LeetCode 中提交一下代码，执行结果如下：

![format_png 9][]

从运行结果来看，二者的执行效率相差还是很明显的：

![format_png 10][]

#### 总结 ####

本文我们讲了一道 bilibili 的笔试真题，同时它也是栈的经典面试题，我们可以借助栈的特性（先进后出）将所有的左括号入栈，当遇到右括号时让它与栈顶元素进行匹配，当字符串循环结束栈为空时，则说明此字符串的括号是合法的。当然我们在实际面试中，也可以使用 Java 的 `replace` 方法作为一个保底的实现方案，因为 `replace` 方法的实现相对更简单一些，只是性能不怎么好。

![format_png 11][]

往期推荐

[![format_png 12][]][format_png 12 1]

[算法图解：如何找出栈中的最小值？][format_png 12 1]

[![format_png 13][]][format_png 13 1]

[链表反转的两种实现方法，后一种击败了100%的用户！][format_png 13 1]

[![format_png 14][]][format_png 14 1]

[JDK 竟然是这样实现栈的？][format_png 14 1]

关注下方二维码，收获更多干货！

![format_png 15][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9TTDlLclVQcXV4U3hYVWoyOW1aRktlakZMYllGMVNhQ3lrc1AwRmljWWV4SlA4S1RmRmxvbTlnLzY0MA?x-oss-process=image/format,png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&idx=1&mid=2247489260&scene=21&sn=c5871b77d084d11319fffc7197be9669#wechat_redirect
[JDK]: https://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&idx=1&mid=2247489510&scene=21&sn=630a6f85d61e4153b4abec40be3b1a3c#wechat_redirect
[100]: https://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&idx=1&mid=2247489569&scene=21&sn=ead310b54ef0b51574c34426b0190d87#wechat_redirect
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&idx=1&mid=2247490115&scene=21&sn=28cd907ca0393cd1ef664a6c21dff78c#wechat_redirect
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9mR0FQV21yeEx4eEZPSWN6ZURkTENyYW9rbTZOZE5GdTV1SnVoVVBYS2ljYlM1bnp0QW1DejFRLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW91amNFOUtnZEU1TGdGbTFEYmxJckdzSHhUWUFPczFZOEJNRndpYjVYOENoN3REeDBXWlFlV05BLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9Na3VtdTJuUWliNjJoT3hpYTVxR2Q1SkVIZUtZc2VpYWtpYUJaem9xY2liVmsxMUFkRklsRHpDSTgzZy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9HclVYbDdHWWdybnBxM09RTFBsQmljdWFwMzYzOHlvVEZuUGI2MmdTaWI0ZXNlMFBFU0YyVFJkUS82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW93dGhpYXpVeU5wbWpJQkFXSTlYa2ljdlRRbjdXdzlNbFpPb2wxQXo1eGNpYmljVTlNWGJSZnRsNUF3LzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9Qd3BVYjFYdFlqYWdhdnYzU3VpY2piVGg1SThHUHJmeDN5UXVkYlhpYWFwU3hBSTY3bG1FMjFHdy82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW81VGhTT2E0aWFjWFBPbFRUazdQZUFPb1VBdEdvWU5pYmxKSlRRSXM0aGVlUUpRNmliYU5TVlc5d1EvNjQw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9Nd2xvMGs2NHNpYjhMMlNXcmFCVGZUYWsyZXhxeFBzajA5akFzSWliNDBSU1d4eEgwa0loVU9pYXcvNjQw?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9tRmF2WVhtaEVIZVR5RnN1T2NZTlhpY3hBdFRpYmx2THJRY2dpYU1XY042elFjZFFHYVU5V25wMGcvNjQw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9Icld3Nlp1WENzaWFnMjhqQm5ZUUY4ODBmTldzT1ptQW9VbGhGWHdJNzhDYXJLS2pxbjdNYWxBWTBBb0VOdHRUMEhTeHM5RTR5NUtpYXVnYmJHYjdqVG9nLzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9iOTZDaWJDdDcwaWFid2p5b2pMaEEwM1B0eFVua05QUkVudDJGNDh5d2ZYTHBEZERBamljT1RQSThROTR0VkxiSjU4dGJSczEyaWFYREtoVU9XOWdkNE5sRkEvNjQw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzaEMzWjdBWUxTdm1HSzBMVTZsRFd1QUk3UTV4WWdXeExWaWJpYURvMkFUdEs2RFc4UHhDMndoSFlrMmljNFE3Wk5BMmt3a1ZyZFlsc1lIZy82NDA?x-oss-process=image/format,png
[format_png 12 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc777bccbbfe6d1af1645942e4ded63424779a83b1a1c7d2d75506d8d1f0fa11f97e645b8d&idx=1&mid=2247490115&scene=21&sn=28cd907ca0393cd1ef664a6c21dff78c#wechat_redirect
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzanJRMWt6ZjZ1cTNoTE1qNG1TQk95Zmh1R3hNd091TVh0WW5iSkFXWDBDOUJqejREcXFPWkpDTjloTXFwOW96SHZ3dk1oNWxiU01YUS82NDA?x-oss-process=image/format,png
[format_png 13 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7519ccbbfc0f847ac650e02419ab813f6a5ea320cc37baac0c227f8fb241990fcbf265bd&idx=1&mid=2247489569&scene=21&sn=ead310b54ef0b51574c34426b0190d87#wechat_redirect
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Icld3Nlp1WENzajhTYUFtQkRBYU9wUEcxdldOcnl1cU9rUkNnRFp6Mko2d0phT3RCRlRtdDZNTGliVFBsMkNhamdwZ0R2MG03T0VTaWJycGJnM29td3NnLzY0MA?x-oss-process=image/format,png
[format_png 14 1]: http://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw%3D%3D&chksm=fbcc7adeccbbf3c8923069b61b7290ca558bbd896d2030fb91bbd8d8ef6f147fa83bec1f9938&idx=1&mid=2247489510&scene=21&sn=630a6f85d61e4153b4abec40be3b1a3c#wechat_redirect
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9zWnlBSnRpYWVzV2NqajRZNmIyUnNZampPNGNtc0E3OXZKY2RyY080RDZxb2t6V1l6NjQ4S2ZQVFNsSWhCeWVKbGZzQmtLaWFzWHR4a2JSTFRUSUxRcGlidy82NDA?x-oss-process=image/format,png