Code ?
On Thu, Jun 5, 2014 at 7:08 PM, kumar raja <[email protected]> wrote: > U have two dimensions for the table ( has O(n^2) entries.) and to check > whether string is palindrome or not it will take O(n) . So it is O(n^3) > solution. > > I have checked it manually for some inputs, and it works. > > > On 5 June 2014 18:53, Shashwat Anand <[email protected]> wrote: > >> I am not too sure about your O (N^3) solution even. Can you link the >> working code ? >> >> >> On Thu, Jun 5, 2014 at 6:48 PM, kumar raja <[email protected]> >> wrote: >> >>> This is a very good collection of DP problems. >>> >>> I want the answers for problem 2(e) >>> and problem 14. >>> >>> for problem 14 the recurrence relation >>> that i have is >>> >>> T[i,j] = 0 if i>=j >>> 1 if j=i+1 and s[i]=s[j] >>> 0 if j=i+1 and s[i]!=s[j] >>> j-i+1/2 if s[i..j] is even length palindrome >>> j-i/2 if s[i..j] is odd length palindrome >>> max{T[i+1,j],T[i,j-1]} else >>> >>> But this is O(n^3) solution. Could not >>> find out solution of order O(n^2). >>> If someone knows please share the answers for them. >>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
