Problem
Given a string s containing only the characters'(', ')', '{', '}', '[', and ']', determine whether the input string is valid.
A string is valid if every opening bracket is closed by the same type of bracket in the correct order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "()[]{}"
Output
true
Solution
This solution uses a Stack to keep track of opening brackets. When an opening bracket is encountered, it is pushed onto the stack.When a closing bracket is encountered, the top element of the stack must contain its corresponding opening bracket. If the stack is empty or the brackets do not match, the string is invalid.
After processing all characters, the string is valid only if the stack is empty.
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.isEmpty();
}
Complexity
The algorithm processes each character exactly once, resulting in a time complexity ofO(n).
In the worst case, all characters may be opening brackets and stored in the stack, resulting in an extra space complexity of
O(n).
