678.有效的括号字符串

class Solution:
    def checkValidString(self, s: str) -> bool:
        N = len(s)

        # dp[i][j] 表示 i 到j能否组成合法的字符串
        dp = [[False for _ in range(N)] for _ in range(N)]
        
        # 仅有一个字符成立的情况
        for i in range(N):
            if s[i] == "*":
                dp[i][i] = True

        # 2个连续字符成立的情况
        for i in range(N-1):
            if (s[i] == "(" or s[i] == "*" )and  (s[i+1] == ")" or s[i+1] == "*" ):
                dp[i][i+1] = True
                    
        for j in range(N):
            for i in range(j-2, -1, -1):
                # 如果两端能组成, 那么就看中间
                if (s[i] == "(" or s[i] == "*" )and  (s[j] == ")" or s[j] == "*" ):
                    dp[i][j] = dp[i+1][j-1]
                # 尝试把整个子数组分成两份
                k = i
                while k < j and not dp[i][j]:
                    dp[i][j] = dp[i][k] and dp[k+1][j]
                    k += 1
        
        return dp[0][N-1]