Valid Parentheses 423
Question
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
Example
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
Solution
用stack实现。遍历string中所有字符,遇到前括号就压入栈中,遇到后括号就看栈顶元素(与该后括号距离最近的前括号)是否和该后括号配对,配对则返回true,不配对或此时stack为空则返回false。
代码如下:
public class Solution {
public boolean isValidParentheses(String s) {
Stack<Character> stack = new Stack<Character>();
for (Character c : s.toCharArray()) {
if ("({[".contains(String.valueOf(c))) {
stack.push(c);
} else {
if (!stack.isEmpty() && is_valid(stack.peek(), c)) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
private boolean is_valid(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
|| (c1 == '[' && c2 == ']');
}
}