Share my python DP solution


  • 0
    Y

    Below is my DP solution in python, ~ 300 ms. O(n) to traverse the DP array. For each subproblem, traverse backwards to find all palindromes, O(n). Checking palindrome takes another O(n). So it seems that my solution is O(n^3). I think the worst case is a string like "aaaaaaaaaaaaaaaaaa ... a".

    Not sure how to reduce to O(n^2). But I like it anyway, because it is consice :)

    EDIT: Actually it is worse than O(n^3), because each step needs to loop through the previous subsolution and do list concatenation on each of them. Sounds like at least O(n^5) ...
    wonder why it can pass the TLE tests

    class Solution:
        # @param s, a string
        # @return a list of lists of string
        def partition(self, S):
            
            def isPalindrome(i, j):
                while i < j:
                    if S[i] != S[j]: return False
                    i += 1
                    j -= 1
                return True
                
            # DP[i] caches all partitions of s[:i]
            # each partition is a list of strings
            DP = [[[]]]
            
            # topological order: from left to right
            for i in xrange(len(S)):
                ptn = []
                # check all possible palindormes ending at s[i]
                for j in reversed(range(i+1)):
                    if isPalindrome(j, i):
                        ptn.extend(q + [S[j:i+1]] for q in DP[j])
                DP.append(ptn)
    
            return DP[-1]

  • 0
    Y

    I see how to reduce the outer O(n^3) loop to O(n^2): using a precalculated palindrome table. (Some other shared solutions used the same idea.)

    But the inner operation of constructing the full partition lists is still expensive. For example, when the input is "aaaaa ... a" (n x 'a'), there are O(n!) ways to partition, so at least we need O(n!) to construct the final result.

    class Solution:
        # @param s, a string
        # @return a list of lists of string
        def partition(self, S):
            
            # pre-calculated palindrome substrings
            palindromes = [[None] * len(S) for _ in xrange(len(S))]
            for i in reversed(range(len(S))):
                for j in xrange(i, len(S)):
                    if j == i:          palindromes[i][j] = True
                    elif j == i + 1:    palindromes[i][j] = (S[i] == S[j])
                    else:               
                        palindromes[i][j] = (
                            palindromes[i + 1][j - 1] and S[i] == S[j]
                        )
    
            # DP[i] caches all partitions of s[:i]
            # each partition is a list of strings
            DP = [[[]]]
    
            # topological order: from left to right
            for i in xrange(len(S)):
                ptn = []
                # check all possible palindormes ending at s[i]
                for j in reversed(range(i+1)):
                    if palindromes[j][i]:
                        ptn.extend(q + [S[j:i+1]] for q in DP[j])
                DP.append(ptn)
    
            return DP[-1]
    

Log in to reply
 

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