20. Valid Parentheses
Model: qwen2.5-coder:14b
Topics: String,Stack
FAANG asked: 1
Acceptance rate: 40.0%
Problem Breakdown
The problem requires determining whether a given string containing only parentheses characters ('(', ')', '{', '}', '[', ']') is valid. A string is considered valid if:
- Open brackets are closed by the same type of brackets.
- Open brackets are closed in the correct order.
Inputs:
- A string
scontaining just the characters'(',')','{','}','[', and']'.
Outputs:
- A boolean value indicating whether the input string is valid or not.
Implicit Constraints/Edge Cases:
- The string can be empty, which should return true as there are no invalid parentheses.
- The string length is between 1 and 10^4 characters.
- The string consists only of the specified parentheses characters.
Intuition
A brute-force approach would involve checking each character in the string to see if it matches a closing parenthesis at some point later in the string. This would be inefficient, as it could potentially require nested loops with a time complexity of O(n^2).
The key insight is that we can use a stack data structure to efficiently match opening and closing parentheses. By pushing each opening parenthesis onto the stack and popping from the stack when a matching closing parenthesis is encountered, we can ensure that both conditions for a valid string are met.
Approach
- Initialize an empty stack.
- Iterate through each character in the string:
- If the character is an opening parenthesis (
'(','{', or'['), push it onto the stack. - If the character is a closing parenthesis (
')','}', or']'):- Check if the stack is empty. If it is, return false as there is no matching opening parenthesis.
- Pop the top element from the stack and check if it matches the current closing parenthesis. If not, return false.
- If the character is an opening parenthesis (
- After processing all characters, check if the stack is empty. If it is, return true; otherwise, return false.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We iterate through each character in the string once.
- Space Complexity: O(n) in the worst case, where all characters are opening parentheses and are pushed onto the stack.
Solution
def isValid(s: str) -> bool:
# Dictionary to hold matching pairs of parentheses
matching_parentheses = {')': '(', '}': '{', ']': '['}
# Stack to keep track of opening parentheses
stack = []
for char in s:
if char in matching_parentheses.values():
# If it's an opening parenthesis, push onto the stack
stack.append(char)
elif char in matching_parentheses.keys():
# If it's a closing parenthesis, check for matching opening parenthesis
if not stack or stack.pop() != matching_parentheses[char]:
return False
# If stack is empty, all parentheses were matched correctly
return not stack
Edge Cases Handled
- Empty String: Returns true as there are no invalid parentheses.
- Single Parenthesis: Returns false as a single parenthesis cannot be closed.
- Nested Parentheses: Handles nested structures like
"{[()]}"correctly. - Mismatched Parentheses: Detects mismatches like
"([)]"and returns false.