Got it. Any idea on how to solve the problem 2(e) ?
On 6 June 2014 00:52, Saurabh Paliwal <[email protected]> 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 <[email protected]> > 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 <[email protected]> >> 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 < >>> [email protected]> 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 [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].
