算法详解版（算法动画第四弹）

文 | 猿天罡

本题源自LeetCode[1]，题号20。

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

示例 2:

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

示例 3:

输入: "(]" 输出: false

示例 4:

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

示例 5:

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

题目的意思是：给定一串括号组成的字符串，让我们判断括号闭合顺序和类型是否正确。

从示例中也可以明白题意。

我们可以用栈结构来解决这道题。栈是先进后出的一种数据结构。如果我们把一些数字顺序存进栈结构中，那么我们取出数字的顺序是和存储顺序相反的。

为了更好地理解栈这种结构，我简单地画了张图。

栈

我们把数字1,2,3,4依次存储到栈的过程称作进栈/压栈，把4,3,2,1依次取出的过程称作出栈/弹栈。

算法具体过程：

1. 初始化栈S。
2. 一次处理给定字符串中的每一个括号。
3. 如果遇到开括号，我们就将其压栈。
4. 如果遇到闭括号，我们就检查栈顶元素（即上图所示栈中最上面的元素）。
5. 如果栈顶元素是一个相同类型的左括号，那么我们将把它从栈中弹出来并继续处理。
6. 否则，这表示给定字符串无效。
7. 如果到最后栈中还剩下元素，也表示给定字符串无效

假设给定的字符串是{[()]}，依照上面的算法，运行过程如下。

有效的括号

如果给定的字符串是{[(]]}，依照上面的算法，运行过程如下。

无效的括号

由于个人精力有限，暂时只提供Java语言代码实现。只要理解了本算法的思想，你也能用其他语言实现出来，这也是对个人代码能力的锻炼。

class Solution { private Map<Character, Character> map; public Solution() { this.map = new HashMap<Character, Character>(); this.map.put(')', '('); this.map.put(']', '['); this.map.put('}', '{'); } public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i ) { char c = s.charAt(i); if (this.map.containsKey(c)) { // 是闭括号 char topElement = stack.isEmpty() ? '#' : stack.pop(); if (topElement != this.map.get(c)) // 括号不匹配 return false; } else { // 开括号 stack.push(c); } } return stack.isEmpty(); } }

5.结语

说到令我们计算机专业最头疼的学科是啥，我猜十有八九会有人投「数据结构」一票，有的算法代码虽然十分简短，可是学起来真的会让人头秃。

除了怀着对计算机行业前辈们的无限憧憬以外，对算法我们其实是敬畏的。

我想，如果能用动画的方式去展示算法运行的过程却是极好的。这样不管是学习还是面试只要脑海中记住动画，心中大体就有了思路。

如果这篇文章对您有所帮助，欢迎点赞、转发加收藏啦~

或者您有任何疑问，可以随时与我联系，感谢您的阅读，我们下期再见。

▼往期精彩回顾 ▼

图解算法：两数之和

图解算法第二弹：整数反转

图解算法第三弹：回文数