leetcode解题: Valid Parenthese (20)

发表于 | 分类于

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

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

解法1： Stack O（N） Space + O（N） Time

主要考察stack的用法，用一个stack存储所有的左括号，每当遇到右括号的时候就取stack中寻找是否是match的左括号。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool isValid(string s) {
        if (s.empty()) {
            return true;
        }
        
        stack<char> st;
        for (auto c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) {
                    return false;
                } else {
                    char top = st.top();
                    if ((top == '(' && c == ')') || (top == '[' && c == ']') || (top == '{' && c == '}')) {
                        st.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        return st.empty();
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        
        Stack<Character> stack = new Stack<Character>();
        
        for (char c: s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if (c == ')' && top == '(') {
                stack.pop();
                } else if (c == ']' && top == '[') {
                    stack.pop();
                } else if (c == '}' && top == '{') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}