题目分析
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.
可以用栈来解决这道题目。时间复杂度为 O(n),空间复杂度为 O(n)。
代码
class Solution {
public boolean isValid(String s) {
if(s == null || s.length() == 0) {
return true;
}
Stack<Character> stack = new Stack();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
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();
}
}
网友评论