Parenthesis String

Parenthesis String in most cases can be solved by using a stack efficiently. However, in some cases, we need advanced technologies such as DP to solve the problem.

678. Valid Parenthesis String

Backtracking solution got TLE

It got TLE as this algorithm has the complexity of O(3^k) k is the number of ‘*’ in the input string. The reason is the backtracking will try all possible ways.

42 / 58 test cases passed. TLE

class Solution:
    def checkValidString(self, s: str) -> bool:
        self.valid = False
        def valid_s(s):
            if not s:return True
            stack = []
            for c in s:
                if c==')':
                    if not stack:return False
                    if stack[-1]!='(':return False
                    else:stack.pop()
                else:
                    stack.append(c)
            #print(stack)
            if not stack:return True
            return False
        def backtracking(s, hist):
            #print(s, hist)
            if not s:
                if valid_s(hist):
                    self.valid = True
            else:
                if not self.valid:
                    if s[0] !='*':
                        backtracking(s[1:], hist+s[0])
                    else:#'*' case
                        backtracking(s[1:], hist+'(')
                        if not self.valid:
                            backtracking(s[1:], hist+')')
                        if not self.valid:
                            backtracking(s[1:], hist)
        backtracking(s, "")
        return self.valid

Backtraping with memo still get TLE

We can change the code a little bit to let it return True or False and at the same time to add the memo for the code. However, it still got TLE.

from functools import lru_cache
class Solution:
    def checkValidString(self, s: str) -> bool:
        def valid_s(s):
            if not s:return True
            stack = []
            for c in s:
                if c==')':
                    if not stack:return False
                    if stack[-1]!='(':return False
                    else:stack.pop()
                else:
                    stack.append(c)
            if not stack:return True
            return False
        @lru_cache(None)
        def backtracking(s, hist):
            if not s:return valid_s(hist)
            if s[0] !='*':
                if backtracking(s[1:], hist+s[0]):return True
                else:return False
            else:
                if any(backtracking(s[1:], hist+cc) for cc in ['(', ')', '']):
                    return True
                return False
        return backtracking(s, "")

DP got AC

The basic idea of DP is

dp[i][j] means whether the s[i:j+1] is valid. We have some cases:

• if i>j: invalid. Valid if i >j. This case happens in the following description.
• if i==j, then dp[i][i] only valid when s[i]==’*’ as * can be treated as empty string.
• if j>i, we have three cases.
• 1) s[i] == ‘(’, it is valid if dp[i+1][k-1] and dp[k+1][j]for k in candidate_indexes, where candidate_indexes are indexes which can make s[k] == ‘)’ or ‘*’ (change ‘*’ into ‘)’ in this case).
• 2) s[i] ==’*’, it is valid if dp[i+1][j] or dp[i+1][k-1] and dp[k+1][j] if s[k]==’)’ or ‘*’
• 3) s[i]==’)’, invalid.

We figure all possible cases and in total, we have n² states. For each state, the worst case, we have to traverse about n subclasses, so the overall complexity is O(n³). n=100 in this problem, so it is doable.

Code is here

from functools import lru_cache
class Solution:
    def checkValidString(self, s: str) -> bool:
        N = len(s)
        @lru_cache(None)
        def dp(i, j):
            # it will touch one edge case whehter i is larger than j. It indicates that the substring is empty.
            if i>j:return True
            if i==j:return s[i]=='*'
            # i < j case
            if s[i] == ')':return False
            if s[i] == '*':
                if dp(i+1, j):return True   
            if s[i] == '(' or s[i]=='*':
                candidates = [k for k in range(i+2,j) if s[k]!='(']
                if s[i+1] != '(':
                    if dp(i+1+1, j):return True
                if s[j]!='(':
                    if dp(i+1, j-1):return True
                return any(dp(i+1,k-1) and dp(k+1,j)  for k in candidates)
return dp(0, N-1)

An even better way

Counting the number of ‘(’. If we encounter a ‘(’, num+=1

if encounter ‘)’, num-=1

if encounter ‘*’, divide it into 3 cases:

• ‘’: num+=0
• ‘(’: num+=1
• ‘)’: num-=1

We should remove the negative value on the fly as it is not OK.

This algorithm has a complexity of O(n²)

class Solution:
    def checkValidString(self, s: str) -> bool:
        # initialize the number of '(' as 0
        res = {0}
        for c in s:
            if c=='(':
                res = {a+1 for a in res}
            elif c==')':
                res = {a-1 for a in res if a-1>=0}
            else: #'*'
                res = {a+k for a in res 
                           for k in [-1, 0 ,1]
                           if a+k>=0}
            if not res:return False
        return 0 in res