共计 2557 个字符，预计需要花费 7 分钟才能阅读完成。
本文已收录至我的 Github《算法图解》系列：https://github.com/vipstone/algorithm
明天要讲的这道题是 bilibili 往年的口试真题，也是一道对于栈的经典面试题。
通过后面文章的学习，我想很多敌人曾经看进去了，我接下来要写的是一个对于「算法图解」的系列文章，两头可能会交叉大量的其余类型的文章，但「算法和数据结构」会是我往年文章输入的重点内容。
我在写这个算法系列的时候会留神两个问题：
- 保障算法的解题思路大家都能看懂，因而我会以图片的模式进行思路解说，这样更直观、更易于了解；
- 在介绍完一个知识点之后，会进行大量的练习，以坚固所学的内容，比方当我讲完「栈」构造之后，我会围绕着「栈」做一系列的经典面试题练习。
学习算法最要害的是把握解题的思路，只有思路对了，编写代码只是工夫的问题。
咱们先来回顾一下往期对于「栈」的内容：
- 《动图演示：手撸堆栈的两种实现办法！》
- 《JDK 居然是这样实现栈的？》
- 《链表反转的两种实现办法，后一种击败了 100% 的用户！》
- 《算法图解：如何找出栈中的最小值？》
那么接下来，咱们就进入明天的正式内容 …
题目
给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否无效。
无效字符串需满足：
- 左括号必须用雷同类型的右括号闭合。
- 左括号必须以正确的程序闭合。
- 留神空字符串可被认为是无效字符串。
示例 1:
输出: “()”
输入: true
示例 2:
输出: “()[]{}”
输入: true
示例 3:
输出: “(]”
输入: false
示例 4:
输出: “([)]”
输入: false
示例 5:
输出: “{[]}”
输入: true
LeetCode 地址：https://leetcode-cn.com/problems/valid-parentheses
解题思路
这道题考查的是就是验证括号的对称性，比方“([{}])”这种字符串就是正确的，应该返回 true，而“([{})]”这种字符串就是谬误的，应该返回 false。
从下面的题目能够看出，括号总共分为三类：小括号、中括号和大括号，那么 咱们能够利用栈先进后出的个性，将所有右边的括号（“(”、“[”、“{”）先入栈，而后再碰到右括号时，让它与栈顶的元素进行匹配，比方当遇到“)”时，如果栈顶是“(”，则阐明匹配胜利，栈顶元素出栈再持续字符串循环的流程，如果匹配谬误就间接返回 false。
假如咱们要匹配字符串“(([]))”是否非法？那么执行流程就是这样的。
首先遇到右边括号，先入栈：
接下来又是右边括号，持续入栈：
而后又是右边括号，持续入栈：
接下来是左边括号，与栈顶元素匹配，“[]”为一对非法的括号，匹配胜利栈顶元素出栈：
接下来又是左边括号，与栈顶元素匹配，“()”为一对非法的括号，匹配胜利栈顶元素出栈：
接下来又是左边括号，与栈顶元素匹配，“()”为一对非法的括号，匹配胜利栈顶元素出栈：
当字符串循环完结并且栈为空栈时，则证实此字符串的括号匹配非法，最终的成果如下图所示：
那么接下来咱们就用代码来实现一下整个过程 …
实现代码一
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 中提交一下代码，执行后果如下：
代码解析
以上代码的 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 中提交一下代码，执行后果如下：
从运行后果来看，二者的执行效率相差还是很显著的：
总结
本文咱们讲了一道 bilibili 的口试真题，同时它也是栈的经典面试题，咱们能够借助栈的个性（先进后出）将所有的左括号入栈，当遇到右括号时让它与栈顶元素进行匹配，当字符串循环完结栈为空时，则阐明此字符串的括号是非法的。当然咱们在理论面试中，也能够应用 Java 的 replace 办法作为一个保底的实现计划，因为 replace 办法的实现绝对更简略一些，只是性能不那么好。
文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。
