NC52 有效括号序列思路分析与代码实现

淡淡的烟草味﹌ 2024-03-02 09:35 8阅读 0赞

### 描述 ###

给出一个仅包含字符'(',')','\{','\}','\['和'\]',的字符串，判断给出的字符串是否是合法的括号序列  
括号必须以正确的顺序关闭，"()"和"()\[\]\{\}"都是合法的括号序列，但"(\]"和"(\[)\]"不合法。

数据范围：字符串长度 0≤n≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

### 示例1 ###

> 输入："\["
> 
> 返回值：false

### 示例2 ###

> 输入："\[\]"
> 
> 返回值：true

### 思路 ###

这道题其实意思很明确，就是括号配对，如果全部配对，那么就是有效的。如果我们仅仅计算这里面各种类型的括号都是偶数个，就认为他们是配对的，那也不对，因为有可能出现 \]\[、)(、\}\{ 的情况。直接统计\[\]、()、\{\}是否都是成对出现也不对，因为有可能有嵌套的形式，比如\[\{()\}\]。

但是不管是那种情况，如果是有效的，那么就是他们不管是单独存在的()\{\}\[\]，还是嵌套出现的\[\{()\}\]，他们有个特点就是如果按照正则匹配来替换删除，那么一个一个替换删除，或者一层一层剥离替换删除，最终得到字符串如果是空，那么就认为是有效的。

()\{\}\[\]和\[\{()\}\]替换删除的效果：

![db91dcef9ca144478d169fe7f5e08d2f.png][]

### 代码 ###

import java.util.*;
    import java.util.regex.*;
    
    
    public class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param s string字符串
         * @return bool布尔型
         */
        public boolean isValid (String str) {
            String reg = "(\\[\\]|\\(\\)|\\{\\})";
            if (str.length() == 0)
                return false;
            if (str.length() % 2 != 0)
                return false;
            Pattern pattern = Pattern.compile(reg);
            boolean stop = false;
            while (true) {
                if (stop)
                    break;
                Matcher matcher = pattern.matcher(str);
                if (matcher.find()) {
                    str = matcher.replaceAll("");
                } else {
                    stop = true;
                }
            }
            if (!"".equals(str))
                return false;
            return true;
        }
    }

实际编码还要考虑如果直接就是空字符串，那么就返回false，字符串个数不成对，也是false。

运行结果：

![43655e46a1db48fca3f6d8d4e072a860.png][]

### 其他解法 ###

另外也给出几个使用栈的思想来解决问题的办法，使用栈，依次遍历字符串，遇到正向(、\[、\{就把反向的)、\]、\}加入栈中， 遇到反向)、\]、\}，如果栈不空，那么栈顶的元素不是当前对应的)、\]、\}，那么就判断无效，并退出循环，如果是，弹出元素，配对成功，继续遍历。如果遍历完成，最终栈为空，那么就认为有效。

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

还有一种使用栈的办法，结合一个map映射: \} -> \{, \] -> \[ , \} -> \{ ，遍历字符串，栈为空，则推入第一个字符，接着遍历后续字符，如果栈顶字符 等于 当前字符对应map映射中的字符，那么就弹出，否则就推当前元素到栈中，遍历完成，判断栈是否为空，为空则表示配对成功，括号序列有效。

public static boolean isValid(String str) {
            Stack<Character> stack = new Stack<>();
            Map<Character,Character> map = new HashMap<>();
            map.put('}','{');
            map.put(')','(');
            map.put(']','[');
            for(int i=0;i<str.length();i++) {
                if(stack.isEmpty()) {
                    stack.push(str.charAt(i));
                    continue;
                }
                if(stack.peek().equals(map.get(str.charAt(i)))) {
                    stack.pop();
                } else {
                    stack.push(str.charAt(i));
                }
            }
            return stack.isEmpty();
        }

使用栈的方式也很容易理解，就是这里对括号的使用有点出人意料，我们通常认为( -> ) 、\[ -> \]、\{ -> \} 这样映射，但是使用栈的时候，我们正好把这个映射弄反，反而更好解决问题。

该题牛客网的地址：[https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2][https_www.nowcoder.com_practice_37548e94a270412c8b9fb85643c8ccc2]

[db91dcef9ca144478d169fe7f5e08d2f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/803000bb3e624c1a88cfbfc76cef67ea.png
[43655e46a1db48fca3f6d8d4e072a860.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/892cc050a5d54752a97bb1b4bf19c398.png
[https_www.nowcoder.com_practice_37548e94a270412c8b9fb85643c8ccc2]: https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2