Approach #1 Use a stack [Accepted]
Intuition
The basic property we're testing for is that brackets are correctly nested. Brackets can nest arbitrarily deep, and in any order, but they must be symmetrically matched. Eg: [(((([{[]}]))))]
This property of arbitrary nesting with symmetry can be very cleanly captured with a stack.
Algorithm
For each character in the string:
if the character is an open paren:
put it on the stack.
Otherwise is a close paren, so:
Attempt to pop off the stack.
If the pop fails:
We have an unbalanced close paren, (eg: `())` therefore:
return False
If the char popped off the stack doesn't match the current closed paren:
return False
If we get to the end of the input string there are still items on the stack:
return False, because we have unbalanced open parens (eg: `(()`.
return True, because our input string has passed all our tests.
Python3
def isValid(s):
brackets = {')': '(', '}': '{', ']': '['}
open_brackets = brackets.values()
stack = []
for char in s:
if char in open_brackets:
stack.append(char)
else:
try:
brackets_match = brackets[char] == stack.pop()
if not brackets_match:
return False
except IndexError:
return False
if stack:
return False
return True
Complexity Analysis
We look at every char in the string. For every char we do a constant amount of work (either putting it on a stack O(1), or popping from the stack O(1) and comparing, O(1)). Therefore total time is O(n), where n is the length of the input string.
 Space complexity : In the worst case half of the chars in the string get placed onto a stack. O(n/2) = O(n), therefore space is O(n).
Pattern matching [Accepted]
Intuition
Another approach is to iteratively remove valid matched parens from the string. If the string is wellformed, there is always at least one innermost pair of parens. If we remove that pair of parens, there should be at least one new innermost pair of parens or the string should be empty. If we cannot remove a pair of matched parens and the string is not empty, then the string cannot be valid.
Algorithm
while there is a pair of matched parens in the string:
replace that pair of parens with the empty string ''.
If the string is the empty string return True, otherwise return False.
Python3
def isValid(s):
while '()' in s or '[]' in s or '{}' in s:
s = s.replace('()', '').replace('[]', '').replace('{}', '')
return s is ''
Complexity Analysis

Time complexity : Each check for the paren pair requires a linear scan of the input string. That means that if there are n chars in the string, we must search through it n/2 times, for a total runtime of O(n^2)

Space complexity: Each time we do a
replace()
call we need to create a new string that, in the worst case, is asymptotically ncharacters long. We only need to hold a reference to one new string at a time, so space storage is O(n)