Valid Parentheses
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.
def is_valid(s: str) -> bool:
# Stack to keep track of opening brackets
stack = []
# Dictionary to map closing brackets to their corresponding opening brackets
mapping = {')': '(', '}': '{', ']': '['}
# Iterate through each character in the string
for char in s:
# If the character is a closing bracket
if char in mapping:
# Pop the topmost element from the stack if it's not empty, otherwise assign a dummy value
top_element = stack.pop() if stack else '#'
# If the popped element doesn't match the corresponding opening bracket
if mapping[char] != top_element:
return False
else:
# If it's an opening bracket, push it onto the stack
stack.append(char)
# If the stack is empty, all brackets were closed correctly; otherwise, return False
return not stackTime 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.
function isValid(s) { const stack = []; for (let i=0; i < s.length; i++) { const char = s.charAt(i); if (['(', '{', '['].includes(char)) { stack.push(char); } else { const top = stack.pop(); if ((char === ')' && top !== '(') || (char === '}' && top !== '{') || (char === ']' && top !== '[')) { return false; } } } return stack.length === 0; }