Leetcode 678 Solution

This article provides solution to leetcode question 678 (valid-parenthesis-string)

https://leetcode.com/problems/valid-parenthesis-string

Solution

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = 0
        hi = 0

        for ch in s:
            if ch == "(":
                lo += 1
                hi += 1
            elif ch == ")":
                hi -= 1
                lo -= 1
            elif ch == "*":
                lo -= 1
                hi += 1
            lo = max(0, lo)

            if hi < 0:
                return False

        return lo <= 0