Valid Parentheses
Easy
Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', write a function isValid to determine if the input string is valid. An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Return true if the string is valid, otherwise return false.
Examples
Input: s = "({" Output: false Input: s = "({[]()})" Output: true
In the first example, all brackets are properly closed and nested, so the result is false. In the second example, each type of bracket is matched and nested correctly, so the result is also true.
Constraints
- The string
shas a length of at most10^4.
Our solution processes the input string by iterating through each character while maintaining a stack to keep track of opening brackets. For each character, it checks if it's a closing bracket. If it is, it pops the topmost element from the stack (if the stack is not empty) and verifies if this element matches the corresponding opening bracket. If it matches, we continue; if not, we return false immediately. If the character is an opening bracket, we push it onto the stack.
After processing all characters, if the stack is empty, it means all opening brackets were properly closed with matching closing brackets, and we return true. If the stack is not empty, it means there are unmatched opening brackets, and we return false.
The solution uses a stack to achieve this efficiently. The stack helps us keep track of the order of opening brackets and ensures that each closing bracket correctly matches the most recent unmatched opening bracket. This approach ensures that each character is processed only once, making it both readable and performant.
Time Complexity: The solution has a time complexity of O(n), where n is the number of characters in the string. This is because we iterate through the string once, performing constant-time operations (stack push/pop and hash map lookups) for each character.
Space Complexity: The solution uses O(n) space for the stack, which stores the opening brackets. In the worst case, if all characters are opening brackets, the stack will contain n entries.
Interview experiences
5 sharedRelated courses
