Valid Parentheses
Problem
Given a string
s
containing just the characters'('
,')'
,'{'
,'}'
,'['
and']'
, 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.
Every close bracket has a corresponding open bracket of the same type.
Pseudocode
Solution
Time and Space Complexity
Time
Loops through string once to find opening and closing parenthesis
Lookup for corresponding parenthesis using Map is constant time
Total - O(N)
Space
Space complexity increases linearly with input i.e. stack length
Total - O(N)
Last updated