My accepted O(n^2) DP solution in Java


  • 5
    M
    public class Solution {
        public int minCut(String s) {
             if(s==null)
                return 0;
             int i,j,n=s.length();
             int cuts[]=new int[n];   //cuts[i] will store the minimum no. of cuts required for substring [0...i];
             boolean dp[][]=new boolean[n][n];   // dp[i][j]=true if substring [i...j] can be partitioned into list of palindromes.
            
            for(i=0;i<n;i++)
            {
                /*since every single character is a palindrome, maximum no. of cuts for substring [0...i] will be i
                 hence initiating cuts[i] with maximum possible value. */        
                 
                cuts[i]=i; 
                for(j=0;j<=i;j++)
                { 
                    if(j == i)
                       dp[j][i] = true;
                    else
                    {
                      if(s.charAt(i)!= s.charAt(j))
                      continue;
                      if(j==i-1)
                      
                      dp[j][i]=true;
                      else
                      dp[j][i]=dp[j+1][i-1] ;
                    }
                    
                  if(dp[j][i])
                  {
                      if(j==0)
                      cuts[i]=0;
                      else
                      cuts[i]=Math.min(cuts[j-1]+1,cuts[i]);  
                     /*since dp[j][i] is a palindrome, cuts[j]+1 equals no. of cuts required in [0...i] if we include the current  word [j..i]; New cuts[i] will be equal to min of previous cuts[i] and the newly calculated cuts[i] i.e. cuts[j]+1 */
                  }
                  
                  
                }
            }
            return cuts[n-1];
            
        }
    }

  • 0
    S

    It's so far the easiest and clearest one to understand


  • 0
    S

    This is a similar way using python.

    class Solution(object):
        def minCut(self, s):
            """
            :type s: str
            :rtype: int
            """
            # cuts is used to store the number of cuts for s[:i+1]. The inital value means to cut every place
            cuts = [i for i in xrange(len(s))]  
    
            # dp[j][i] is used to store if s[j:i+1] is palindrome. We initialize everything to False except those on diagonal
            dp = [[False if i!=j else True for i in xrange(len(s))] for j in xrange(len(s))]
    
            for i in xrange(len(s)):
                for j in xrange(i+1):
                    if s[i]==s[j]:
                        # if there are no more letters between j and i, then we assign True, else move "inside" one step
                        dp[j][i] = True if i-j<=1 else dp[j+1][i-1]
                        if dp[j][i]:
                            # because s[j:i+1] is palindrome, we can update cuts[i]
                            cuts[i] = 0 if j==0 else min(cuts[j-1]+1, cuts[i])
            return cuts[-1]

Log in to reply
 

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