My python DP solution

  • 0
    class Solution(object):
    def isMatch(self, s, p):
        :type s: str
        :type p: str
        :rtype: bool
        lenS, lenP = len(s), len(p)
        # dp[i][j]==True means s[:i] matches p[:j]
        dp = [[False]*(lenP+1) for i in xrange(lenS+1)]
        dp[0][0] = True
        for si in xrange(lenS+1):  # starting from 0, which inits the dp[0][:]
            for pi in xrange(1, lenP+1):  # starting from 1
                if p[pi-1] != '*':
                    dp[si][pi] = si>0 and dp[si-1][pi-1] and (s[si-1]==p[pi-1] or p[pi-1]=='.')
                else:  # handle '*'
                    # matches zero time or more than once
                    dp[si][pi] = dp[si][pi-2] or (si>0 and dp[si-1][pi] and (s[si-1]==p[pi-2] or p[pi-2]=='.'))
        return dp[lenS][lenP]

Log in to reply

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