Got it. Any idea on how to solve the problem 2(e) ?
On 6 June 2014 00:52, Saurabh Paliwal <saurabh.paliwa...@gmail.com> wrote: > T[i][j] = 0 (i < 0 || j >=n || i >= j || s[i] != s[j]) > > T[i][j] = 1 + T[i-1][j+1] > > > > > On Fri, Jun 6, 2014 at 12:19 AM, kumar raja <rajkumar.cs...@gmail.com> > wrote: > >> If i get u correctly, this is the recurrence relation ( i feel this makes >> many people to understand the solution rather than looking at the code) >> >> >> T[i..j] indicates the length of longest even length palin string ( not >> exactly palin but i think u know what i am saying) with i as begin and j as >> ending point. >> >> T[i,j] = 0 if i>=j >> T[i+1,j-1]+1 if s[i]==s[j] >> 0 else >> >> And u find max value in the table which is the answer >> >> So time complexity = space complexity = O(n^2). >> >> Correct me if i am wrong >> >> >> >> On 5 June 2014 23:44, Saurabh Paliwal <saurabh.paliwa...@gmail.com> >> wrote: >> >>> And now I get what you meant when you said "palindrome". You should have >>> explained that if that was "not exact palindrome" >>> >>> So yes, your solution seems correct but that is the brute force >>> approach. It runs in O(n*n*n) as there are n*n substrings and every check >>> is linear. DP solution helps save time by memoization. >>> >>> >>> On Thu, Jun 5, 2014 at 11:37 PM, Saurabh Paliwal < >>> saurabh.paliwa...@gmail.com> wrote: >>> >>>> Ok! So I guess now we are talkng my solution. What i do is maintain two >>>> pointers i and j, i is the end of the first string and j is the beginning >>>> of the second. If both the character match, I calculate the answer for >>>> pointers i-1,j+1 and add 1 to the answer for i,j. If they don't match, I >>>> simply mark 0 as the answer for i,j. So my table if filled top-down like >>>> this. Finally, I return the maximum entry in the table. >>>> Need I explain further? If so, feel free. Should I explain what those >>>> methods do? >>>> >>> >>> >>> >>> -- >>> - 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. >> > > > > -- > - 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.
