Wrong answer for "bb" input.


  • 0
    K

    Below is my python dp solution for palindrome partition II.

    Recursion Pseudo Code:

    1. Assign i=0,j= N-1
    2. minCut(S,0,N-1) = 0 (if Palindrome)
    3. else min(1 + minCut(s,1,N-1) ,1 + minCut(s,0,N-2))

    The code seems to work fine for all the inputs except "bb" , which returns 1 for OJ instead of 0. But the solution works correctly and returns 0 in my system. Not sure what is wrong with the evaluation. Any help is appreciated. Thanks.

    class Solution:
            # @param s, a string
            # @return a list of lists of string
            part_dict = {}
            def minCut(self, s):
                return self.dp_compute_partition(s,0,len(s)-1)
        
            def dp_compute_partition(self, s,i,j):
                if (i , j) in self.part_dict:
                    return self.part_dict[(i , j)]
                if i > j:
                    self.part_dict[(i , j)] = 0
                elif s[i] == s[j]:
                    self.part_dict[(i,j)] = self.dp_compute_partition(s,i + 1,j-1)
                else:
                    self.part_dict[(i,j)] = min(1 + self.dp_compute_partition(s,i+1,j), 1 + self.dp_compute_partition(s,i , j-1))
                return self.part_dict[(i, j)]

Log in to reply
 

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