有效的括号

梦里梦外; 2023-06-23 13:21 16阅读 0赞

题目：

> 给定一个只包括 '('，')'，'\{'，'\}'，'\['，'\]' 的字符串，判断字符串是否有效。
> 
> 有效字符串需满足：
> 
> 左括号必须用相同类型的右括号闭合。
> 
> 左括号必须以正确的顺序闭合。
> 
> 注意空字符串可被认为是有效字符串。
> 
> 示例 1:
> 
> 输入: "()"
> 
> 输出: true
> 
> 示例 2:
> 
>  
> 
> 输入: "()\[\]\{\}"
> 
> 输出: true
> 
> 示例 3:
> 
>  
> 
> 输入: "(\]"
> 
> 输出: false
> 
> 示例 4:
> 
>  
> 
> 输入: "(\[)\]"
> 
> 输出: false
> 
> 示例 5:
> 
>  
> 
> 输入: "\{\[\]\}"
> 
> 输出: true

思路：

> 1. 使用栈的先进后出的数据结构，为ture的情况下，括号都是成对出现的，并且左半边括号是先出现的（代码实现：代码1）；
> 
> 2. 递归成对的括号，使用正则将成对的括号替换为‘’，判断结果是否为‘’(代码实现：代码2)；

代码1：
    public static boolean isValid(String s) {
    
        if (s.length() % 2 != 0) {
            return false;
        }
    
        List<Character> l = new ArrayList<>(3);
        l.add('(');
        l.add('[');
        l.add('{');
    
        Stack<Character> stack = new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (l.contains(c)) {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                switch (c) {
                    case ')':
                        if (stack.pop() != '(') {
                            return false;
                        }
                        break;
                    case ']':
                        if (stack.pop() != '[') {
                            return false;
                        }
                        break;
                    case '}':
                        if (stack.pop() != '{') {
                            return false;
                        }
                        break;
                }
            }
        }
        return stack.isEmpty();
    }

代码2
    public static boolean isValid(String s) {
            while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
                s = s.replaceAll("\\(\\)","");
                s = s.replaceAll("\\[\\]","");
                s = s.replaceAll("\\{\\}","");
            }
            return s.equals("");
        }