20. 有效的括号

分手后的思念是犯贱 2023-10-13 22:29 18阅读 0赞

### 20. 有效的括号 ###

*  题干背景
 *  重要思路
 *  代码实现

# 题干背景 #

[力扣入口 - 20.有效的括号][- 20.]

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。  
示例 1:

输入: “()”  
输出: true  
示例 2:

输入: “()\[\]\{\}”  
输出: true  
示例 3:

输入: “(\]”  
输出: false  
示例 4:

输入: “(\[)\]”  
输出: false  
示例 5:

输入: “\{\[\]\}”  
输出: true

# 重要思路 #

1.  Java中的Stack基本被抛弃，我们考虑使用Deque这种双端队列来替代Stack，具体实现是`Deque<Character> deque = new LinkedList<>()`。
2.  碰到左括号则入栈对应右括号，碰到右括号处理三种情况，前两种在过程中判断，判断当前栈是否为空以及队首的元素是否需要的括号。最后结尾处再根据栈是否为空，即有无剩余，来判断是否有效。

# 代码实现 #

// 20. 有效的括号
    public boolean isValid2(String s){
        
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for(int i = 0; i < s.length(); i++){
        
            ch = s.charAt(i);
            // 碰到左括号，就把相应的右括号入栈
            if(ch == '('){
        
                deque.push(')');
            } else if(ch == '{'){
        
                deque.push('}');
            } else if(ch == '['){
        
                deque.push(']');
            } else if(deque.isEmpty() || deque.peek() != ch){
         // 右括号多余了，左侧无对应 | 括号类型不匹配
                return false;
            } else{
        
                deque.pop();
            }
        }
        // 最后判断栈中元素是否匹配 - 应对第一种情况(字符串里左方向的括号多余了)
        return deque.isEmpty();
    }

**参考资料**：[20. 有效的括号][20.]

[- 20.]: https://leetcode.cn/problems/valid-parentheses/description/
[20.]: https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html#%E9%A2%98%E5%A4%96%E8%AF%9D