[Java·算法·简单]LeetCode20. 有效的括号

柔情只为你懂 2023-09-24 20:51 15阅读 0赞

#### 每天一题，防止痴呆 ####

*  题目
 *  示例
 *  分析思路1
 *  题解1
 *  分析思路2
 *  题解2

## 题目 ##

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

有效字符串需满足：  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
每个右括号都有一个对应的相同类型的左括号。

## 示例 ##

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

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

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

## 分析思路1 ##

使用栈来判断括号的匹配情况。遍历字符串中的每个字符，当遇到左括号时，将其压入栈中。当遇到右括号时，需要检查栈顶的左括号是否和它匹配。如果不匹配或栈为空，说明字符串不合法。如果匹配，将栈顶的左括号出栈。遍历结束后，如果栈为空，说明字符串合法。

## 题解1 ##

class Solution {
        
        public boolean isValid(String s) {
        
    
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {
        
                if (c == '(' || c == '[' || c == '{') {
        
                    stack.push(c);
                } else {
        
                    if (stack.isEmpty()) {
        
                        return false;
                    }
                    char top = stack.pop();
                    if (c == ')' && top != '(') {
        
                        return false;
                    }
                    if (c == ']' && top != '[') {
        
                        return false;
                    }
                    if (c == '}' && top != '{') {
        
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }

执行结果  
![在这里插入图片描述][01c40102219b44e584f8e6f66fa0ac59.png]

## 分析思路2 ##

使用`String.replace`方法直接将`()`替换为空。  
(效率太低，不太可取，但是是最简单的方法)

## 题解2 ##

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

执行结果

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

[01c40102219b44e584f8e6f66fa0ac59.png]: https://img-blog.csdnimg.cn/01c40102219b44e584f8e6f66fa0ac59.png
[73cf585101f14dc4b73963b08e311705.png]: https://img-blog.csdnimg.cn/73cf585101f14dc4b73963b08e311705.png