Rephrasing Divya's solution. Basic idea is to find center of palindrom string and then verify. step 1: Pass through entire array, if we get two same character back to back, call that position as center-k. At max you can have n-1 such centers. This takes O(N).
step-2: For each center check surrounding string on both left and right side. Keep track of length. This step takes O(N) in worst case. Combining step 1 and 2, you get O(N^2) On Sun, Jun 6, 2010 at 9:30 AM, Rohit Saraf <[email protected]> wrote: > Just read your code. It wont even work. > Do you assume only one even length palindrome!? > > -- > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
