LeetCode_栈_简单_20.有效的括号

- 日理万妓 2023-10-06 18:36 66阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。  
有效字符串需满足：  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。

**示例 1：**  
输入：s = “()”  
输出：true

**示例 2：**  
输入：s = “()\[\]\{\}”  
输出：true

**示例 3：**  
输入：s = “(\]”  
输出：false

**示例 4：**  
输入：s = “(\[)\]”  
输出：false

**示例 5：**  
输入：s = “\{\[\]\}”  
输出：true

**提示：**  
1 <= s.length <= 104  
s 仅由括号 ‘()\[\]\{\}’ 组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-parentheses

## 2.思路 ##

（1）栈  
判断括号的有效性可以使用**栈**这一数据结构：  
① 先创建好一个栈 **stack**，刚开始时栈为空，并且开始遍历字符串；

② 如果当前字符 c1 为任意一个左括号（即’('，‘\[’，‘\{’中的任意一个），则将其压入栈中，并且继续遍历；

③ 否则就判断栈是否为空，如果栈为空，则说明当前遍历到的右括号（任意一个都是）在栈中没有对应的左括号，所以配对失败，直接返回 false 即可；如果栈不为空，则取出栈顶字符并赋值给 c2，要想配对成功，c2 必须时与 c1 匹配的左括号，所以根据它们的 ASCII 值的组合可以判断是否有效。如果有效则返回步骤 ② 继续遍历，知道遍历结束或直接返回结果为止；

④ 如果遍历结束，当栈为空时，说明全部的括号已经按顺序配对完成，返回true，否则说明栈中还有多余的括号，则返回 false。

相关题目：  
[LeetCode\_递归\_回溯算法\_中等\_22.括号生成][LeetCode_22.]  
[LeetCode\_栈\_动态规划\_困难\_32.最长有效括号][LeetCode_32.]  
[LeetCode\_回溯\_困难\_301. 删除无效的括号][LeetCode_301.]  
[LeetCode\_栈\_中等\_856.括号的分数][LeetCode_856.]  
[LeetCode\_栈\_中等\_921.使括号有效的最少添加][LeetCode_921.]

## 3.代码实现（Java） ##

//思路1————栈
    class Solution {
        
        public boolean isValid(String s) {
        
            //字符串长度为奇数时，不可能配对成功，直接返回false即可
            if (s.length() % 2 != 0) {
        
                return false;
            }
            Stack<Character> stack = new Stack<>();
            char c1, c2;
            int temp;
            for (int i = 0; i < s.length(); i++) {
        
                c1 = s.charAt(i);
                if (c1 == '(' || c1 == '[' || c1 == '{') {
        
                    //将字符c1添加到栈中
                    stack.add(c1);
                } else {
        
                    if (stack.isEmpty()) {
        
                        return false;
                    } else {
        
                        //取出栈顶元素并赋值给c2
                        c2 = stack.pop();
                        temp = 0 + c1 + c2;
    	                /* 
    	                	各个括号的ASCII值如下：
    	                   '(':40  ')':41  '[':91  ']':93  '{':123  '}':125
    	                   取出的括号如果能够正确配对，则只会它们的 ASCII 值之和只会出现 81、184 和 248 这 3 种情况
    	                */
                        if (temp != 81 && temp != 184 && temp != 248) {
        
                            return false;
                        }
                    }
                }
            }
            //遍历结束后，当栈为空时，说明全部的括号已经按顺序配对完成
            return stack.isEmpty();
        }
    }

//另一种写法
    class Solution {
        
        public boolean isValid(String s) {
        
            //字符串长度为奇数时，不可能配对成功，直接返回false即可
            if (s.length() % 2 != 0) {
        
                return false;
            }
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {
        
                if (c == '(' || c == '[' || c == '{') {
        
                    //字符c为左括号时，将其压入栈顶
                    stack.push(c);
                } else {
        
                    //字符为右括号
                    if (!stack.isEmpty() && stack.peek() == getLeftBracket(c)) {
        
                        //取出栈顶元素
                        stack.pop();
                    } else {
        
                        //不匹配时直接返回false
                        return false;
                    }
                }
            }
            //遍历结束后，当栈为空时，说明全部的括号已经按顺序配对完成
            return stack.isEmpty();
        }
        
        //获取右括号c对应的左括号
        public char getLeftBracket(char c) {
        
            if (c == ')') {
        
                return '(';
            } else if (c == ']') {
        
                return '[';
            } else {
        
                return '{';
            }
        }
    }

[LeetCode_22.]: https://blog.csdn.net/weixin_43004044/article/details/123493807
[LeetCode_32.]: https://blog.csdn.net/weixin_43004044/article/details/122975965
[LeetCode_301.]: https://blog.csdn.net/weixin_43004044/article/details/125029726
[LeetCode_856.]: https://blog.csdn.net/weixin_43004044/article/details/127220452
[LeetCode_921.]: https://blog.csdn.net/weixin_43004044/article/details/127160064