Valid Parenthesis

problem at:

# 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.


  • Time:
  • Space:

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:
        elif len(stack) and c==dict.get(stack[-1]):
            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==""