Stack. Time = O(n), space = O(n)
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')') {
if (stack.isEmpty() || stack.peek() != '(') {
return false;
}
stack.pop();
} else if (c == ']') {
if (stack.isEmpty() || stack.peek() != '[') {
return false;
}
stack.pop();
} else if (c == '}') {
if (stack.isEmpty() || stack.peek() != '{') {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}