Python DP & BackTracking


  • 0

    First to try once DP very similar to 10 Regular Expression Matching, actually TLE before using this piece of code, which I got from other folks of the discuss:

            count = 0
            for i in xrange(len(p)):
                if p[i] != '*':
                    count += 1
            if count > len(s):
                return False
    

    Even if it seems a hacky way to cheat the OJ, but at least allow me post the less efficient "solution" here:

    class Solution(object):
        def isMatch(self, s, p):
            count = 0
            for i in xrange(len(p)):
                if p[i] != '*':
                    count += 1
            if count > len(s):
                return False
            dp = [ [False for i in xrange(len(p) + 1)] for j in xrange(len(s) + 1) ]
            dp[0][0] = True
            for i in xrange(len(p)):
                if p[i] == '*':
                    dp[0][i + 1] = True
                else:
                    break
            for i in xrange(len(s)):
                for j in xrange(len(p)):
                    if p[j] != '*':
                        dp[i + 1][j + 1] = (s[i] == p[j] or p[j] == '?') and dp[i][j]
                    else:
                        dp[i + 1][j + 1] = dp[i + 1][j] or dp[i][j] or dp[i][j + 1]
            return dp[-1][-1]
    

    Then will be the back-tracking solution, the basic idea is that when there is a miss match, go back to the pre-nearest '*' and move one step more of s.

    class Solution(object):
        def isMatch(self, s, p):
            idxs, idxp, rs, rp = 0, 0, -1, -1
            while idxs < len(s):
                if idxp < len(p):
                    if s[idxs] == p[idxp] or p[idxp] == '?':
                        idxs, idxp = idxs + 1, idxp + 1
                    elif p[idxp] == '*':
                        idxp, rp, rs = idxp + 1, idxp + 1, idxs + 1
                    else:
                        if rs == -1:
                            return False
                        idxs, idxp, rs = rs, rp, rs + 1
                else:
                    if rs == -1:
                        return False
                    idxs, idxp, rs = rs, rp, rs + 1
            while idxp < len(p) and p[idxp] == '*':
                idxp += 1
            return idxp == len(p)
    

Log in to reply
 

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