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].
