Use stack to check if the close parenthesis match with the open parenthesis.
Time complexity: O( len(s) )
Space complexity: O( len(s) )
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character, Character> pairs = new HashMap<>() {
{
put('(', ')');
put('[', ']');
put('{', '}');
}
};
for (char a : s.toCharArray()) {
if (pairs.containsKey(a)) {
stack.push(a);
} else {
if (stack.isEmpty() || pairs.get(stack.pop()) != a) return false;
}
}
return stack.isEmpty();
}
}
Edited on 03/12/2022. Use map to pair brackets.
No comments:
Post a Comment