U need not get an exact palindrome. u will start comparing from both the end points till they are equal and does not cross each other. So that should be possible in linear time right. I did not get ur code exactly and u have written O(n*n) so i have got the doubt.
On 5 June 2014 23:22, Saurabh Paliwal <[email protected]> wrote: > Dude! That is what I just posted. Also your logic is wrong, Palindrome > thing is just not working. Think for a while on this problem. > > > On Thu, Jun 5, 2014 at 11:18 PM, kumar raja <[email protected]> > wrote: > >> 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 <[email protected]> >> 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 <[email protected]> wrote: >>> >>>> 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]. >>>> >>> >>> >>> >>> -- >>> - 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 [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]. >> > > > > -- > - 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 [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].
