LeetCode 题解-20. Valid Parentheses

对Leetcode 20. Valid Parentheses 题目的求解。

Problem Description#

Given a string containing just the characters ’(’, ’)’, ’{’, ’}’, ’[’ and ’]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order. Note that an empty string is also considered valid.

Example#

Example 1

1
Input: "()"
2
Output: true

Example 2

1
Input: "()[]{}"
2
Output: true

Example 3

1
Input: "(]"
2
Output: false

Example 3

1
Input: "([)]"
2
Output: false

Analysis#

这道题比较简单，只需要使用栈这种数据结构就可以轻松解决。遇到左括号，我们push进栈，遇到右括号，如果此时栈为空或者栈顶不是对应的左括号，我们即可判断匹配失败。如果是对应的左括号，那么pop出栈顶。然而我发现使用java自带的栈的代码只能在leetcode上超过60%的时间复杂度，说明我们代码还有提升空间。进一步考虑使用数组来代替java数据结构，我们只需要创建一个足够大的数组（不需要考虑扩张以及banlance factor），并且记录栈顶的位置即可。

更进一步的观察我们发现，由于需要考虑三种不同的括号，我们不得不对三个括号的匹配进行列举，使得代码冗长。如果我们在push进栈时将我们期待的右括号push进去，那么我们在后续匹配时就不用遍历三种可能的情况，而是直接比较当前括号和栈顶括号是否相同即可。

Solution#

1
class Solution {
2
    public static boolean isValid(String s) {
3
        if (s.length() == 0) return true;
4
        if (s.length() % 2 == 1) return false;
5
        Stack<Integer> st = new Stack<Integer>();
6
        for (int i = 0; i < s.length(); ++i){
7
            if (s.charAt(i) == '('){
8
                st.push(0);
9
            }
10
            else if(s.charAt(i) == '{'){
11
                st.push(2);
12
            }
13
            else if (s.charAt(i) == '['){
14
                st.push(4);
15
            }
16
            else if (s.charAt(i) == ')'){
17
                if (! st.isEmpty() && st.peek() == 0){
18
                    st.pop();
19
                }
20
                else return false;
21
            }
22
            else if (s.charAt(i) == '}'){
23
                if (! st.isEmpty() && st.peek() == 2){
24
                    st.pop();
25
                }
26
                else return false;
27
            }
28
            else {
29
                if (! st.isEmpty() && st.peek() == 4){
30
                    st.pop();
31
                }
32
                else return false；
33
            }
34
        }
35
        return st.isEmpty();
36
    }
37
}

Optimized Solution#

1
class Solution {
2
    public static boolean isValid(String s) {
3
        if (s.length() == 0) return true;
4
        if (s.length() % 2 == 1) return false;
5
        //Stack<Character> st = new Stack<Character>();
6
        char arr[] = new char[s.length()];
7
        int ind = -1;
8
        // store what we expected
9
        for (int i = 0; i < s.length(); ++i){
10
            if (s.charAt(i) == '('){
11
                arr[++ind] = ')';
12
            }
13
            else if (s.charAt(i) == '{'){
14
                arr[++ind] = '}';
15
            }
16
            else if (s.charAt(i) == '['){
17
                arr[++ind] = ']';
18
            }
19
            else if (ind >= 0 && arr[ind] == s.charAt(i)){
20
                ind --;
21
            }
22
            else {
23
                return false;
24
            }
25
        }
26
        return ind == -1;
27
    }
28
}