Valid Parentheses and Stack (Easy) | LeetCode Practice #5

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

Enter fullscreen mode Exit fullscreen mode

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.