Valid Parentheses
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.
Python
####Replace Function (Runtime: 225ms, Memory: 12.4MB)
#DECLARE s: STRING
class Solution(object):
def isValid(self, s):
while "()" in s or "[]" in s or "{}" in s:
s = s.replace("()", "")
s = s.replace("[]", "")
s = s.replace("{}", "")
if len(s) == 0:
return True
return False
####Stack (Runtime: 7ms, Memory: 12.4MB)
#DECLARE s: STRING
class Solution(object):
def isValid(self, s):
pair_map = {")": "(", "]": "[", "}": "{"}
stack = []
for char in s:
if not stack or stack[-1] != pair_map.get(char):
stack.append(char)
else:
stack.pop()
if len(stack) == 0:
return True
return False
####Recursion (Runtime: 579ms, Memory: 416MB)
#DECLARE s: STRING
class Solution(object):
def isValid(self, s):
self.pair_map = {"(": ")", "[": "]", "{": "}"}
arr = list(s)
return self.recursionMethod(1, arr)
def recursionMethod(self, scan_index, arr):
if len(arr) == 0:
return True
for i in range(scan_index, len(arr)):
if arr[i] == self.pair_map.get(arr[i-1]):
arr.pop(i)
arr.pop(i-1)
scan_index = max(1, i-2)
return self.recursionMethod(scan_index, arr)
return False
Thoughts
Not going to lie, but the first method that came to my mind was Recursion. I actually looked forward to using Recursion, but the data slapped me hard in the face. The question is meant to be solved using Stack methods, and it's hard to work around that.
SOCIAL SHARE CARD GENERATOR