20.有效的括号【简单】

àì夳堔傛蜴生んèń 2022-10-06 08:59 89阅读 0赞

# 20. 有效的括号 【简单】 #

给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
**左括号必须以正确的顺序闭合。**

**示例 1：**

输入：s = "()"
    输出：true

**示例 2：**

输入：s = "()[]{}"
    输出：true

**示例 3：**

输入：s = "(]"
    输出：false

**示例 4：**

输入：s = "([)]"
    输出：false

注意：这里如果`()`中间插入了`{}`或`[]`,这样也不算是有效的字符串。这里要尤其注意，不能单一的使用对对消的方法。本题使用堆栈是最有效的方式。（我就是对对消了半天，发现错了）

**示例 5：**

输入：s = "{[]}"
    输出：true

**提示：**

>  *  1 <= s.length <=  10 4 \{10\}^4 104
>  *  `s` 仅由括号 ‘`()[]{}`’ 组成

## JAVA代码： ##

### 基本方法： ###

思路：用`“”`替换一对符号，也能防止一对符号穿插显示的无效情况。  
缺点：速度慢，内存消耗大  
优点：神回路，棒！没想到

class Solution { 
    
        public boolean isValid(String s) { 
             int length = s.length()/2;
             for(int i = 0;i<length;i++){ 
                 s = s.replace("()","").replace("{}","").replace("[]","");
    
             }
             return s.length()==0;
        }
    
    }

![在这里插入图片描述][20210612154419904.png]

### 堆栈方法： ###

class Solution { 
    
        public boolean isValid(String s) { 
    
            int n = s.length();
            if(n%2==1){ 
                return false;
            }
    
             //栈
             Deque<Character> stack = new LinkedList<Character>();
    
            //保存括号对
             Map<Character,Character> map = new HashMap<Character,Character>(){ { 
                 put('{','}');
                 put('[',']');
                 put('(',')');
             }};
             
             //左括号入栈，右括号就和栈顶比较，匹配就出栈。
             for(int i = 0;i<n;i++){ 
                 char ch = s.charAt(i);
                 if(map.containsKey(ch)){ 
                      //入栈
                      stack.push(ch);
                 }else{ 
                     //判断是否与栈顶括号匹配
                     //peek()和pop()的区别：都返回栈顶元素，但是pop()同时会删除栈顶元素，而peek()不会。
                     if(stack.isEmpty()||map.get(stack.peek())!=ch){ 
                          return false;
                     }
                     //出栈
                     stack.pop();
                 }
             }
             //栈为空时，为有效的括号。
             return stack.isEmpty();
        }
    
    }

![在这里插入图片描述][20210612154526712.png]

**解题思路图解参考（很清晰）：**

> 题解：https://leetcode-cn.com/problems/valid-parentheses/solution/yuan-lai-hui-luo-ji-qing-xi-jian-dan-yi-yjcme/

**关于为什么新建一个栈，使用Deque而不使用Stack：**

*  1.由于Vector由于效率问题已经被弃用，因此继承Vector的Stack也存在效率问题，故不推荐使用。
 *  2.Deque**双端队列**可以实现多种数据结构，完全可以模拟成栈的结构。

> 参考资料：https://www.cnblogs.com/code-duck/p/13569388.html

[20210612154419904.png]: /images/20221005/a0b669811b734bbeba9b7330c9f236f8.png
[20210612154526712.png]: /images/20221005/a099d7986fb6480ba98b2c0203436cc5.png