鲁达 文 | 猿天罡
本题源自LeetCode[1]，题号20。
1.题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true示例 2:
输入: "()[]{}" 输出: true示例 3:
输入: "(]" 输出: false示例 4:
输入: "([)]" 输出: false示例 5:
输入: "{[]}" 输出: true2.解题思路
题目的意思是：给定一串括号组成的字符串，让我们判断括号闭合顺序和类型是否正确。
从示例中也可以明白题意。
我们可以用栈结构来解决这道题。栈是先进后出的一种数据结构。如果我们把一些数字顺序存进栈结构中，那么我们取出数字的顺序是和存储顺序相反的。
为了更好地理解栈这种结构，我简单地画了张图。
栈
我们把数字1,2,3,4依次存储到栈的过程称作进栈/压栈，把4,3,2,1依次取出的过程称作出栈/弹栈。
算法具体过程：
- 初始化栈S。
- 一次处理给定字符串中的每一个括号。
- 如果遇到开括号，我们就将其压栈。
- 如果遇到闭括号，我们就检查栈顶元素（即上图所示栈中最上面的元素）。
- 如果栈顶元素是一个相同类型的左括号，那么我们将把它从栈中弹出来并继续处理。
- 否则，这表示给定字符串无效。
- 如果到最后栈中还剩下元素，也表示给定字符串无效
3.算法动画
假设给定的字符串是{[()]}，依照上面的算法，运行过程如下。
有效的括号
如果给定的字符串是{[(]]}，依照上面的算法，运行过程如下。
无效的括号
4.代码实现
由于个人精力有限，暂时只提供Java语言代码实现。只要理解了本算法的思想，你也能用其他语言实现出来，这也是对个人代码能力的锻炼。
class Solution { private Map<Character, Character> map; public Solution() { = new HashMap<Character, Character>(); .put(')', '('); .put(']', '['); .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 (.containsKey(c)) { // 是闭括号 char topElement = () ? '#' : (); if (topElement != .get(c)) // 括号不匹配 return false; } else { // 开括号 (c); } } return (); } }5.结语
说到令我们计算机专业最头疼的学科是啥，我猜十有八九会有人投「数据结构」一票，有的算法代码虽然十分简短，可是学起来真的会让人头秃。
除了怀着对计算机行业前辈们的无限憧憬以外，对算法我们其实是敬畏的。
我想，如果能用动画的方式去展示算法运行的过程却是极好的。这样不管是学习还是面试只要脑海中记住动画，心中大体就有了思路。
如果这篇文章对您有所帮助，欢迎点赞、转发加收藏啦~
或者您有任何疑问，可以随时与我联系，感谢您的阅读，我们下期再见。
▼往期精彩回顾 ▼
图解算法：两数之和
图解算法第二弹：整数反转
图解算法第三弹：回文数