Valid Parenthesis

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)$
space: $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==""