给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
使用栈的经典题目，我们将所有的左括号入栈，当遇到右括号时，如果栈为空或者栈顶元素不能与当前括号匹配，返回false。遍历到最后，如果栈为空则 返回 true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '(' || c == '[' || c == '{'){
stack.push(c);
}else if(c == ')'){
if(stack.size() == 0 || stack.pop() != '(') return false;
}else if(c == ']'){
if(stack.size() == 0 || stack.pop() != '[') return false;
}else{
if(stack.size() == 0 || stack.pop() != '{') return false;
}
}
return stack.isEmpty();
}
}
|
时间复杂度O(n)，空间复杂度O(n)。