20 有效括号
题目信息
题目地址：https://leetcode-cn.com/problems/valid-parentheses
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
题解一
要满足括号的规则，那么一个括号里面不能有残缺的括号。那么对于{[]}它是一个括号且包含一个子括号，如果当当前括号完整时，子括号仍不完整即为false.
我们可以用包含自己和子节点的结构来去记录，就是一个链表，要必须按照顺序一个一个匹配完成，否则就false
class Node{
Node child;
}
遍历到一个左括号，那么就产生了一个node,之后要么产生node作为child要么是消除。直到最后没有node
([)]
1 #左括号
1 2 #又一个左括号
1 fail #出现右括号但不匹配
{[]}
1 #左括号
1 2 #又一个左括号
1 #出现右括号匹配消除
success #出现右括号匹配消除，最后一个也消除了
还是画个动图吧
总而言之，如果是左括号就加到列表当中，如果是右括号就要和最头上的一个进行比较，能配上就消除否则false，最后消除完毕一个都不剩则满足true
代码一：
class Node{
char value;
Node next;
Node(char value){
this.value = value;
}
}
public boolean isValid(String s) {
// 1.括号数据
Map<Character,Integer> left = new HashMap();
left.put('(',1);
left.put('[',2);
left.put('{',3);
Map<Character,Integer> right = new HashMap();
right.put(')',1);
right.put(']',2);
right.put('}',3);
// 2.自定义链表
Node cur = null;
// 3.遍历处理
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
// 如果左括号加节点，右括号看是否能消除
if(left.containsKey(c)){
// 入列
Node pre = new Node(c);
pre.next = cur;
cur = pre;
}else if(cur != null && right.get(c).equals(left.get(cur.value))){
// 消除
cur = cur.next;
}else{
return false;
}
}
boolean result = cur == null ? true : false;
return result;
}
这里相当于我们自己去实现了一个数据结构，每次只能拿到头部，当头部消除我们可以拿到头部的前一个（next），通过头插的方式来实现。
当然我们也可以直接用我们语言提供的现有的数据结构的库类，比如JAVA里有栈的实现Stack。思路是一样的，只不过封装好的栈结构我们直接拿来用push、pop等来完成我们的逻辑，不必实现基础的节点加入、消除等操作的具体节点关系的实现。
代码二：
public boolean isValid(String s){
// 1.括号数据
Map<Character,Integer> left = new HashMap();
left.put('(',1);
left.put('[',2);
left.put('{',3);
Map<Character,Integer> right = new HashMap();
right.put(')',1);
right.put(']',2);
right.put('}',3);
// 2.栈
Stack<Character> stack = new Stack<>();
// 3.遍历处理
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
// 判定左括号还是右括号
if(left.containsKey(c)){
stack.push(c);
}else if(stack.isEmpty() || !right.get(c).equals(left.get(stack.pop()))){
return false;
}
}
boolean result = stack.empty() ? true : false;
return result;
}
代码逻辑都是大差不差，但对于括号的匹配我们是用map存储，且明显感到有冗余。都用值来去匹配感觉自己有点脑瘫了，直接key-value匹配就行少一个获取值的步骤了。
代码三：
public boolean isValid(String s){
// 1.括号数据
Map<Character,Character> map = new HashMap();
map.put('(',')');
map.put('[',']');
map.put('{','}');
// 2.栈
Stack<Character> stack = new Stack<>();
// 3.遍历处理
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
// 判定左括号还是右括号
if(map.containsKey(c)){
stack.push(c);
}else if(stack.isEmpty() || !map.get(stack.pop()).equals(c)){
return false;
}
}
return stack.empty();
}
在有限的条件范围，我们要追求更高的效率非要钻这个牛角尖的话，是有固定方式就是手动列举。当然其实没必要，举例下：
代码四：
public boolean isValid(String s){
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c=='('||c=='['||c=='{'){
stack.push(c);
}else if(stack.isEmpty()||c==')'&&stack.pop()!='('||c==']'&&stack.pop()!='['||c=='}'&&stack.pop()!='{'){
return false;
}
}
return stack.empty();
}
那么有个问题，难道就没有一种方既可以直接比较得出是否是一对（不需要建立映射加扫描的方式），又不是手动去把情况都列出来。
那就是ascii码，好像很有道理，ascii不就是天然的字符映射关系么，我们拿这个映射的值能不能判断呢。
那么去找了一下ascii码，可以得到结论在这六个符号组成的字符串当中，它们之间的差值是1或者2，那么只有是一对括号才能出现。我们之前自己通过map构建映射关系现在其实字符本身就有映射内容且其实可以判断出来
代码五
public boolean isValid(String s){
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c=='('||c=='['||c=='{'){
stack.push(c);
}else if(stack.empty()){
return false;
}else if(c-stack.peek()==1 || c-stack.peek()==2){
stack.pop();
}else{
return false;
}
}
return stack.empty();
}
题解二
题解二是在看了官方评论区了解的另一种思路，是从字符串着手的
public boolean isValid(String s) {
while(true){
int l=s.length();
s=s.replace("()","");
s=s.replace("{}","");
s=s.replace("[]","");
if(s.length()==l){return l==0;}
}
}
它效率可能不高，但确实没想到这个思路。它效率低的问题在于每次需要遍历三次字符串进行匹配替换，确实每次都遍历整个串进行替换完完全全的提高了一个维度变成2次方了相当于是走了弯路属于暴力解法。
总结
虽然不难但其实还是有挺多有趣的想法，关于提高效率的定式以及两个字符匹配比较的核心由建立映射转移到天然映射ascii码的，在原有体会的情况下相当于再一次加深了印象抽取出思维方式。此题第一是一个解决过程的思路第二是过程知道了但在细节步骤里面是如何判断匹配这又会引发很多思考，首先想到的是map映射进行匹配两个字符，将没有关系的两个字符关联，但我们自己建立映射确实可以有更多的扩展，但我们有没有考虑字符本身就存在映射，天然的映射能不能为我所用这是专注一点的时候可以考虑到的。
往期推荐
腾讯云开发者
