[Leetcode][第20题][JAVA][有效的括号][栈][HashMap]

快来打我* 2022-11-27 15:37 108阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

###### 1. 栈 ######

如果是一个合法的括号序列，遍历到一个右括号(i)时，那么它的前一个括号(i-1)必定是它的另一半(左括号)。反之不是它的另一半或者前面没有括号时，那这个序列必定是非法括号序列。  
思路：利用一个stack辅助保存括号，遇见左括号时入栈对应的右括号，遇到右括号时

*  栈空，证明前面没有匹配括号 多余的右括号
 *  栈非空弹出栈顶元素进行比较操作  
    最后判断栈是否为空
 *  空 括号匹配
 *  非空 多余的左括号

**要么在入栈时根据不同类别入栈右括号 要么出栈的时候根部不同类别作判断 至少进行一次分类讨论**  
**时间复杂度：O(N) 空间复杂度：O(N)**

优秀代码
    class Solution { 
        public boolean isValid(String s) { 
            
            int len = s.length();
            if (s == null || len == 0) return true;
        	if (len % 2 != 0) { 
            // 如果长度为奇数，必然至少有一个括号没有匹配
            	return false;
        	}
            Deque<Character> stack = new ArrayDeque<>();
            for (char ch : s.toCharArray()) { 
                if (ch == '(') { 
                    stack.addLast(')');
                } else if (ch == '[') { 
                    stack.addLast(']');
                } else if (ch == '{') { 
                    stack.addLast('}');
                } else if (stack.isEmpty() || stack.removeLast() != ch) { 
                    return false;
                }
            }
            return stack.isEmpty();
        }
    }

public boolean isValid(String s) { 
          
            if(s.isEmpty())
                return true;
            Stack<Character> stack=new Stack<Character>();
            int n = s.length();
            for(int i = 0;i<n;i++){ 
                char a = s.charAt(i);
              
                if(a=='(')
                    stack.push(')');
                else if(a=='{')
                    stack.push('}');
                else if(a=='[')
                    stack.push(']');
                else{ 
                    if(stack.isEmpty()||stack.pop()!=a ){ 
                        return false;
                    }
                }
            }
    
            return stack.isEmpty();
        }

借助栈，对字符串进行字符遍历，如果字符是左括号，则入栈，左括号为’(’，’\{’，’\[’，如果字符是右括号，则出栈，并将右括号与左括号联合比较，判断是否可以组成有效的括号，有效括号是"()"，"\{\}"，"\[\]"，如果不能组成，则返回错误

class Solution { 
        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 { 
                    char p = stack.empty() ? '\0' : stack.pop();
                    if ((c == '}' && p != '{') || (c == ']' && p != '[')
                            || (c == ')' && p != '(')) { 
                        return false;
                    }
                }
            }
            return stack.empty();
        }
    }

###### 2. HashMap ######

**时间复杂度：O(N) 空间复杂度：O(1)**

public boolean isValid(String s) { 
        if (s == null) { 
            // 如果输入字符为空没有必要继续下去，直接返回false
            return false;
        }
        int len = s.length();
        if (len % 2 != 0) { 
            // 如果长度为奇数，必然至少有一个括号没有匹配
            return false;
        }
        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < len; i++) { 
            char current = s.charAt(i);
            if (pairs.containsKey(current)) { 
                // 如果栈已经为空了，说明右括号比左括号多，不匹配，直接返回false
                // 当第一次出现右括号的时候， 栈顶元素必然为左括号，不然不匹配，直接返回false
                if (stack.isEmpty() || stack.peek() != pairs.get(current)) { 
                    return false;
                }
                stack.pop();
            } else { 
                stack.push(current);
            }
        }
        // 如果最后栈不为空，说明左括号多于右括号，不匹配，返回false
        return stack.isEmpty();
    }

#### 【总结】 ####

###### 1. 优化 ######

**1.1 判断长度为奇数时 直接返回错误**  
**1.2 使用Deque 代替 stack**  
stack在基于数组实现上效率低 扩容效率低

初始化
    Deque<Character> stack = new ArrayDeque<>();
    Deque<Character> stack = new LinkedList<>();

**1.3 字符串转z字符数组遍历 速度较快**

String s;
    char[] ch=s.toCharArray()；

###### 2.Deque ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

参考文章：https://www.cnblogs.com/lxyit/p/9017350.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/6a42bf339f2f485d9ec241700ba467a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/685b439cdd1b4bcf9fea27f6b8627ebe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/35b4e6a8cf8e40408b732dc34b0c0600.png