Question
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.
Stats
| Frequency | 5 |
| Diffficulty | 2 |
| Adjusted Difficulty | 3 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
Either stack or string would work.
Solution
The code is easy.
My code
public class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return false;
}
Stack<Character> stack = new Stack<Character>();
// process s char by char
for (char c: s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
// eg. input = "())))"
return false;
}
char top = stack.pop();
if (Math.abs(top - c) > 2) {
// parentheses does not match
return false;
}
}
}
// after this, stack should be empty (if parentheses valid)
return stack.isEmpty();
}
}