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