Valid Parenthesis

https://leetcode.com/problems/valid-parentheses

# Solution

The stack solution is preferred over the string replace one.

# Stack

In Python, stack is [] and dictionary is {}.

Add '(', '{', '[' into stack, if the corresponding closing sign matches with stack top, pop the stack. Finally, check if stack is empty.

Complexity:

  • Time: O(n)O(n)
  • Space: O(n)O(n)

where n is the length of s.

def isValid(self, s: str) -> bool:
    # build a dict
    dict = {
        "(": ")",
        "[": "]",
        "{": "}"
    }

    stack = []
    for c in s:
        if c in dict:
            stack.append(c)
        elif len(stack) and c==dict.get(stack[-1]):
            stack.pop()
        else:
            return False
    return len(stack)==0

# String Replace

Use Python's str.replace method, but runtime would be much slower.

def isValid(self, s: str) -> bool:
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()","").replace("[]","").replace("{}","")
    return s==""
Last Updated: 7/19/2020, 3:45:14 PM