Codes and explains of DP solution using python


  • 0
    T

    Thanks to @ChuntaoLu 's solution.
    Based on his solution I wrote these codes and comments which I think are more understandable and easy-to-read in the first glimpse.
    Hope this can help people who has no idea how to start with DP solution

    class Solution(object):
        def isMatch(self, s, p):
            p = Solution.removeConsecutive('*', p)
            return self.isMatchHelper(s, p)
    
        # a little bit of optimization
        @staticmethod
        def removeConsecutive(mark, p):
            i = 0
            while i < len(p):
                if i+1 < len(p) and p[i] == mark and p[i+1] == mark:
                    p = p[0:i] + p[i+1:]
                else:
                    i += 1        
            return p
    
        def isMatchHelper(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            DP = [True] + [False for _ in range(len(s))]
            for i in range(1, len(p)+1):
                next_itr = [DP[0] and p[i-1] == '*'] + [False for _ in range(len(s))]
                for j in range(1, len(s)+1):
                    if p[i-1] == '?':
                        next_itr[j] = DP[j-1]
                    elif p[i-1] == '*':
                        next_itr[j] = DP[j] or next_itr[j-1]
                    else:
                        next_itr[j] = DP[j-1] and p[i-1] == s[j-1]
                DP = next_itr
    
            return DP[-1]
    
    # For a 2d table, dp[i][j] would mean whether sub-pattern p[:i] matches sub-string s[:j].
    # Most tricky part is when the current pattern letter is *, suppose its index is i-1, p[:i] will 
    # match sub-string s[:j] if p[:i] matches s[:j-1] or p[:i-1] matches s[:j], namely current
    # cell value is true if its top or its left is true. Since the current row only depends on the previous 
    # row, we can use two rolling lists to do the dp instead of a matrix.
    #
    # so the pseudo code of 2d dp solution would be:
    
    # initial DP[0][:]
    # for i = 1:len(p)
    #     for j = 1:len(s)
    #         if p[i-1] is '?':
    #             DP[i][j] = DP[i-1][j-1]
    #         if p[i-1] is regular character:
    #             DP[i][j] = DP[i-1][j-1] and p[i-1] equals s[j-1]
    #         if p[i-1] is '*':
    #             DP[i][j] = ( DP[i][j-1]     // since '*' can represent multiple characters
    #                         or DP[i-1][j]   // since '*' can represent empty characters
    # return DP[end][end]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.