20. Valid Parentheses

Posted on | In |

LeetCode 20. Valid Parentheses

基础括号匹配问题。括号匹配肯定要用栈。栈里存什么呢？这个题目里栈里存当前期望的右括号最合适。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    for (char c : chars) {
        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();
}

如果在循环结束前栈已为空或者出现了不匹配的括号，则返回false。只有循环结束后栈为空才返回true，如果循环结束后栈不为空则返回false。