Valid Parentheses [Solution]
This problem assesses the your ability to work with string manipulation and correctly use the stack data structure to solve a problem.
Below is a Python implementation of the is_valid_parentheses
function to determine if the input string contains valid parentheses:
def is_valid_parentheses(s: str) -> bool:
"""
Determine if the input string contains valid parentheses.
Parameters:
- s: Input string.
Returns:
- bool: True if the parentheses are valid, False otherwise.
"""
stack = [] # Stack to keep track of open parentheses
parentheses_map = {')': '(', '}': '{', ']': '['} # Mapping of closing to opening parentheses
for char in s:
if char in parentheses_map.values():
# If the character is an open parenthesis, push it onto the stack
stack.append(char)
elif char in parentheses_map:
# If the character is a closing parenthesis
# Check if the stack is not empty and the top of the stack matches the corresponding open parenthesis
if not stack or stack.pop() != parentheses_map[char]:
return False
else:
# If the character is neither open nor closing parenthesis, return False
return False
# The parentheses are valid if the stack is empty
return not stack
# Example usage:
s1 = "()"
result1 = is_valid_parentheses(s1)
print(result1) # Output: True
s2 = "()[]{}"
result2 = is_valid_parentheses(s2)
print(result2) # Output: True
s3 = "(]"
result3 = is_valid_parentheses(s3)
print(result3) # Output: False
s4 = "([)]"
result4 = is_valid_parentheses(s4)
print(result4) # Output: False
s5 = "{[]}"
result5 = is_valid_parentheses(s5)
print(result5) # Output: True
This solution uses a stack to keep track of open parentheses as they are encountered in the string. It checks if the closing parentheses match the corresponding open parentheses.
Time Complexity:
The time complexity is O(n)
, where n
is the length of the input string.
Space Complexity:
The space complexity is O(n)
due to the stack.