is O(n) solution possible
________________________________ From: abhijith reddy <[email protected]> To: [email protected] Sent: Friday, 6 May 2011 9:47 PM Subject: Re: [algogeeks] dp1[i][j] will hold 1/0 depending upon whether string str[i...j] is a palindrome or not. Now let dp2[i][j] be the minimum number of cuts required to split it into palindromes. if str[i...j] is a palindrome then '0' cuts are required. To get the number of cuts required for str[i...j] we try all possible positions between i & j and take minimum of all. On Fri, May 6, 2011 at 8:23 PM, sourabh jakhar <[email protected]> wrote: can you explain the logic > > > >On Fri, May 6, 2011 at 8:02 PM, abhijith reddy <[email protected]> >wrote: > >O(N^3) DP >>------------------------------------------------------------------------------------------------------------- >>char str[MAX]; >>int dp1[MAX][MAX],dp2[MAX][MAX]; >> >>int isPalin(int low,int high) >>{ >> if(low>=high) return 1; >> if(dp1[low][high]!=-1) return dp1[low][high]; >> return dp1[low][high]=(str[low]==str[high])?isPalin(low+1,high-1):0; >>} >> >>int minCuts(int low,int high) >>{ >> if(isPalin(low,high)) return 0; >> if(dp2[low][high]!=-1) return dp2[low][high]; >> int ans=1e9; >> for(int i=low;i<high;i++) >> ans=min(ans,1+minCuts(low,i)+minCuts(i+1,high)); >> return dp2[low][high]=ans; >>} >> >>------------------------------------------------------------------------------------------------------------- >> >> >> >>On Fri, May 6, 2011 at 4:23 PM, sourabh jakhar <[email protected]> >>wrote: >> >>You are given a large string. You need to cut the string into chunks such >>that each substring that you get is a palindrome. Remember that each 1 length string is always a palindrome. You need to find the minimum number of cuts that you need to make such that each substring is a palindrome. >>> >>>-- >>>SOURABH JAKHAR,(CSE)(3 year) >>>ROOM NO 167 , >>>TILAK,HOSTEL >>>'MNNIT ALLAHABAD >>> >>> >>>The Law of Win says, "Let's not do it your way or my way; let's do it the >>>best way." >>> -- >>>You received this message because you are subscribed to the Google Groups >>>"Algorithm Geeks" group. >>>To post to this group, send email to [email protected]. >>>To unsubscribe from this group, send email to >>>[email protected]. >>>For more options, visit this group at >>>http://groups.google.com/group/algogeeks?hl=en. >>> >> -- >>You received this message because you are subscribed to the Google Groups >>"Algorithm Geeks" group. >>To post to this group, send email to [email protected]. >>To unsubscribe from this group, send email to >>[email protected]. >>For more options, visit this group at >>http://groups.google.com/group/algogeeks?hl=en. >> > > >-- >SOURABH JAKHAR,(CSE)(3 year) >ROOM NO 167 , >TILAK,HOSTEL >'MNNIT ALLAHABAD > > >The Law of Win says, "Let's not do it your way or my way; let's do it the best >way." > -- >You received this message because you are subscribed to the Google Groups >"Algorithm Geeks" group. >To post to this group, send email to [email protected]. >To unsubscribe from this group, send email to >[email protected]. >For more options, visit this group at >http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
