Yes i agree that my recurrence relation is wrong. I have checked it some inputs, it did not work. But i think the brute force solution is possible in O(n^3) solution. We have O(n^2) combination of end points. we can check for the maximum possible even length palin string in O(n). So that will give O(n^3). Anyone has solution about O(n^2)?
On 5 June 2014 22:25, Saurabh Paliwal <saurabh.paliwa...@gmail.com> wrote: > Hi all! > Well, I agree with Shashwat in that Kumar is wrong with his solution. For > example a string " kumarxyzramuk " will tell you why. > I have a solution which runs in O(n*n) time. It is top-down dynamic > programming approach. Let me know if you don't understand something or if > there is some glitch in the solution. I think it is correct. > > Link to the C++ code - http://ideone.com/Qzs990 > > > On Thu, Jun 5, 2014 at 7:13 PM, Shashwat Anand <m...@shashwat.me> wrote: > >> Code ? >> >> >> On Thu, Jun 5, 2014 at 7:08 PM, kumar raja <rajkumar.cs...@gmail.com> >> 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 <m...@shashwat.me> 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 <rajkumar.cs...@gmail.com> >>>> 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 algogeeks+unsubscr...@googlegroups.com. >>>>> >>>> >>>> -- >>>> 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 algogeeks+unsubscr...@googlegroups.com. >>>> >>> >>> -- >>> 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 algogeeks+unsubscr...@googlegroups.com. >>> >> >> -- >> 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 algogeeks+unsubscr...@googlegroups.com. >> > > > > -- > - Saurabh Paliwal > > B-Tech. Comp. Science and Engg. > > IIT ROORKEE > > -- > 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 algogeeks+unsubscr...@googlegroups.com. > -- 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 algogeeks+unsubscr...@googlegroups.com.
