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.
No doubt, this problem is supposed to solve using 'stack'.
My solution takes 58 ms. And then, I found the top solution is really beautiful and only takes 9 ms! So…
public static boolean isValid(String s) {
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < s.length(); i++) {
int n = 99;
if (s.charAt(i) == '(')
n = 1;
if (s.charAt(i) == '[')
n = 2;
if (s.charAt(i) == '{')
n = 3;
if (s.charAt(i) == ')')
n = -1;
if (s.charAt(i) == ']')
n = -2;
if (s.charAt(i) == '}')
n = -3;
int lastone = 99;
if (!stack.isEmpty())
lastone = stack.lastElement();
System.out.println(lastone);
if (lastone + n == 0) {
stack.pop();
} else {
stack.push(n);
}
}
if (stack.isEmpty())
return true;
return false;
}
public static boolean isValidTop(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c : s.toCharArray()) {
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();
}