Valid Parenthesis String

---

Intuition

• Every ) must have a ( or a * before it. Therefore, check for every ) whether that’s the case in place.
• Every ( if it doesn’t have a ), must have a * after it.

Complexity

Runtime

$O(N)$, where N is the number of wildcards

Space

$O(N)$

Code

class Solution:
    def checkValidString(self, s: str) -> bool:
        paren_stack = []
        star_stack = []
 
        for i, c in enumerate(s):
            if c == '*':
                star_stack.append(i)
            elif c == ')':
                if paren_stack:
                    paren_stack.pop()
                elif star_stack:
                    star_stack.pop()
                else:
                    return False
            else:
                paren_stack.append(i)
 
        while star_stack:
            star_pos = star_stack.pop()
            if not paren_stack:
                return True
            paren_pos = paren_stack.pop()
            if paren_pos > star_pos: # *(
                return False
 
        return len(paren_stack) == 0

Notes

Drive

Cards

START Basic Front: Valid Parenthesis String Back: Every ) must have a ( or a * before it. END

---

References

• Valid Parenthesis String