Python dynamic programming solution TLE


  • 0
    P

    Here is my solution. Similar to other DP solutions but in Python.
    OJ: Last executed input: "pcighfdjnbwfkohtklrecxnooxyipj", "npodkfchrfpxliocgtnykhxwjbojie"
    I wrote a pure recursive Python solution and it is accepted but not DP solution.
    Anyone knows why?

    class Solution:
        # @return a boolean
        def isScramble(self, s1, s2):
            if sorted(s1)!=sorted(s2):
                return False
            else:
                n=len(s1)
            dp=[[[s1[j]==s2[k] if i==0 else False for i in range(n)] for j in range(n)]for k in range(n)]
            for L in range(2,n+1):
                for i in range(n-L+1):
                    for j in range(n-L+1):
                        for m in range(1,L):
                            if dp[i][j][L-1]:
                                break
                            dp[i][j][L-1]=(dp[i][j][m-1] and dp[i+m][j+m][L-m-1]) or (dp[i+m][j][L-m-1] and dp[i][j+L-m][m-1])
            return dp[0][0][n-1]

  • 0
    G

    Same thing happened to me. On my laptop the code runs for less than 0.1s.
    Can you post your recursive solution?

    class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        if not len(s1) == len(s2):
            return False
        N = len(s1)
        dp = [ [ [ None for ___ in xrange(N+1) ] for __ in xrange(N+1) ] \
                for _ in xrange(N+1)]
        for i in xrange(0, N):
            for j in xrange(0, N):
                dp[i][j][1] = bool(s1[i] == s2[j])
        # length of substring for examination
        for l in xrange(1, N+1):
            # loop through starting pos of s1
            for i in xrange(0, N-l+1):
                # loop through starting pos of s2
                for j in xrange(0, N-l+1):
                    # position to cut
                    for p in xrange(1, l):
                        # left of s1 cut is-scramble left of s2 cut
                        # and right of s1 cut is-scramble right of s2 cut
                        a = dp[i][j][p] and dp[i+p][j+p][l-p]
                        # left of s1 cut is-scramble right of s2 cut
                        # and left of s1 cut is-scramble right of s2 cut
                        b = dp[i][j+l-p][p] and dp[i+p][j][l-p]
                        dp[i][j][l] = bool(a or b)
        return dp[0][0][N]
    

Log in to reply
 

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