20 Valid Parentheses

1. Question

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.

2. Implementation

思路:查看括号匹配问题,就看相应的符号是否对称,可以直接用stack做
1
class Solution {
2
public boolean isValid(String s) {
3
Stack<Character> stack = new Stack<>();
4
5
for (char c : s.toCharArray()) {
6
if (c == '(') {
7
stack.push(')');
8
}
9
else if (c == '[') {
10
stack.push(']');
11
}
12
else if (c == '{') {
13
stack.push('}');
14
}
15
else if (stack.isEmpty() || (stack.pop() != c)) {
16
return false;
17
}
18
}
19
return stack.isEmpty();
20
}
21
}
Copied!

3. Time & Space Complexity

时间和空间都是O(n)