算法训练 第一周

二、有效的括号

本题给出了一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，要求我们我们判断这个字符串中的左右括号能否完全匹配，简单来说就是一个左括号必须要有一个和它对应的右括号，如果不能完全匹配就返回false。本题主要是考察对栈的应用，最普遍的解法就是用栈了。

1.栈

我们在遍历这个字符串的时候，只需要遇到左括号就往栈中存入相应的右括号，遇到右括号就弹出栈顶的括号与它比较，此时会出现三种不匹配的情况：

一、弹出的栈顶括号与遍历到的右括号不相同，此时返回false。

二、当遇到右括号时栈中为空，说明没有与此右括号匹配的左括号，返回false。

三、当遍历完整个数组时栈中还有元素，说明有剩余的左括号没有与之匹配的右括号，返回false。
当我们遍历完整个数组后，没有返回false就说明此字符串有效。具体代码如下：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> sta = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '{'){
                sta.push('}');
            } else if(s.charAt(i) == '['){
                sta.push(']');
            } else if(s.charAt(i) == '('){
                sta.push(')');
            } else if(!sta.empty()){
                if(sta.pop() != s.charAt(i)){
                    return false;
                }
            } else {
                return false;
            }
        }
        if(!sta.empty()){
            return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
• 空间复杂度：O(n)。

2.消除法

我们可以循环遍历这个字符串，如果遇到"{}“，”[]“，”()“，就将它们用”“代替，重复此过程直到字符串不再包含上述三种子串，此时如果字符串为”"就说明所有的括号都有对应的匹配，就返回true，如果字符串不为空，就说明有些括号没有对应的匹配，此时就返回false。具体代码如下：

class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        if(len % 2 != 0) {
            return false;
        }
        for(int i = 0; i < len / 2; i++) {
            s = s.replace("{}","").replace("[]","").replace("()","");
        }
        return s.equals("");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

因为我们每次执行一组replace操作都会使字符串的长度减2，所以我们只需最多进行字符串的长度一半次数的操作就可以得出结果。

复杂度分析

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n)。