括号匹配专题
你可否记得，当年被【括号匹配】支配的恐惧？
>>> 本文先讨论最基本的括号匹配及其经典的【栈】思路
>>> 再分析其变体
>>> 最后是究极变体，从【栈】【动态规划】【括号计数（追赶法）】三种方法切入，彻底理解括号匹配问题
>>>
>>> 记住，所有的方法，归根结底还是从括号字符串的自身特性出发的
>>> 再记住两句话：
>>> 1.【尝试用')'去消去前面的'('】
>>> 2.【当右括号数量超过左括号时，必然串无效】
经典的栈
/*
* 经典的【栈】思路
*
* 遇到'('，就入栈; 遇到')'，就出栈
* 扫描过程中，当出栈时发现栈空时，串无效
* 扫描结束后。若栈空，则串有效；如果栈不空，则串有效
*/
public boolean isValid(String s) {
Deque
for(char c : s.toCharArray()) {
if(c == '(') {
stack.push(c);
}else {
if(stack.isEmpty()) {
return false;
}else {
stack.pop();
}
}
}
return stack.isEmpty();
}
变体1——不止是小括号
思路变体：【经典的栈】 + 【Map】
▊【Q20】(ez) 有效的括号(括号匹配问题) 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]'的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1: 输入: “([{}])” 输出: true 示例 2: 输入: “([)]” 输出: false
class Solution {
public boolean isValid(String s) {
/*
* 思路：
* 如果是左括号，就毫不犹豫的入栈；
* 如果是右括号，不仅要先判断是否栈空，还要判断弹出的左括号是否对应此时的右括号
*
* 注：
* 1.使用HashMap进行匹配，使得代码和逻辑都更具美感
* 2.典型的栈结构问题。由于java 8,9有移除Stack的趋势，因此这里使用双端队列Deque，同样有PushPop特性
*/
if(s == null || s.length() == 0) return true; // leetcode传统艺能，null和0值不说就是true
Map
map.put(')', '(');
map.put(']', '[')