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.
public boolean isValid(String s) {
if (s.length() % 2 != 0)
return false;
char[] characters = new char[s.length()];
int index = 0, i;
for (i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(')
characters[index++] = s.charAt(i);
if (s.charAt(i) == '[')
characters[index++] = s.charAt(i);
if (s.charAt(i) == '{') {
characters[index++] = s.charAt(i);
System.out.println(index);
}
if (s.charAt(i) == ')') {
if (--index < 0 || characters[index] != '(')
break;
}
if (s.charAt(i) == ']') {
if (--index < 0 || characters[index] != '[')
break;
}
if (s.charAt(i) == '}') {
if (--index < 0 || characters[index] != '{')
break;
}
}
if (i == s.length() && index == 0)
return true;
return false;
}
方法通过了,不过觉得有点笨,暂时也没想到好的,先就这样啦。LeedCode也没给我们提供详解。
找到一个写得比较好的程序,极力推荐大家不要看我的,看这个,又感觉被甩了几条街。
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 == ']');
}
用了系统的栈,我用的数组栈。