@above The new string that you need to create will be of size -> 2*N - sizeof(LCS)
On Dec 16, 7:55 pm, Lucifer <[email protected]> wrote: > @topcoder > > Time complexity = O(N*N) > Space complexity = O(N*N) > > Once you have figured out the LCS you can also trace from the array > LCS[N*N] , used to calculate the LCS, the exact pairs LCS(i,j) which > represent the LCS chars.. > > Say for LCS(x,y), > x-> represents the index in the original string "OrigStr" and y -> > represents the index in the reversed string "RevStr"... > > Now, say the path is (0,0) , (x1, y1) , (x2, y2), ..... (xN, yN) , (N > -1 , N -1) > I have added the first and last pair to basically accommodate the > special cases like "dabae"... reverse of "dabae" would be "eabad" > > Now, all we need to do is sequentially access the list and do the > following: > Given 2 pairs (xi, yi) and (x i+1, y i+1), > We will insert RevStr(yi .. y i+1) , excluding the extreme chars, just > before Str(x i+1)... > > Corner cases like checking the char set being empty etc can be handled > once you write the code. Also you need to create a new string and keep > copying both LCS chars and the RevStr chars accordingly... > > On Dec 16, 2:20 pm, top coder <[email protected]> wrote: > > > > > > > > > @Lucifer > > > I have got the intent of your logic. > > > From the algo, We got to know how many characters need to be added. > > How do you concluded where do you need to add the characters exactly > > and What characters needs to be added? > > Also Could you comment on the time and space complexity? > > > On Dec 15, 11:37 am, Lucifer <[email protected]> wrote: > > > > Correction: > > > > for NAN : > > > N(IT)A + TI + N = NITATIN > > > > On Dec 15, 11:33 am, Lucifer <[email protected]> wrote: > > > > > @topcoder.. > > > > > String: NITAN > > > > > RevStr: NATIN > > > > > LCS ( NITAN, NATIN) = { NIN , NAN } > > > > > Here all we care about the count which is 2. Hence, 2 additions would > > > > be required to convert it into a palindrome.. > > > > > The possible palindromes would be: > > > > for NIN : > > > > N + AT + I(TA)N = NATITAN > > > > > for NAN : > > > > N + TI+ A(IT)N = NATITAN > > > > > On Dec 15, 11:24 am, top coder <[email protected]> wrote: > > > > > > @Mohit > > > > > > Suppose for example > > > > > > String: NITAN > > > > > LCS(Longest Common Subsequence) : NIN > > > > > > How do you get the palindrome with it? > > > > > > On Dec 15, 3:47 am, Lucifer <[email protected]> wrote: > > > > > > > @Mohit > > > > > > > I think what he meant is 2* strlen("Input String") - 2* ("Length of > > > > > > LCS") > > > > > > > On Dec 15, 3:44 am, Mohit kumar lal <[email protected]> wrote: > > > > > > > > @saurabh-as by the above example LCS of "HELLO" and its inverse > > > > > > > would be > > > > > > > "LL" and how can we form the word "HELLOLLEH" with it ... > > > > > > > and is your ans for the word "NITAN" is "NITATIN" ...? > > > > > > > > On Wed, Dec 14, 2011 at 8:39 PM, saurabh singh > > > > > > > <[email protected]> wrote: > > > > > > > > Find the LCS of string with its reverse.... > > > > > > > > > On Wed, Dec 14, 2011 at 8:33 PM, top coder > > > > > > > > <[email protected]> wrote: > > > > > > > > >> Given a word, convert it into a palindrome with minimum > > > > > > > >> addition of > > > > > > > >> letters to it. letters can be added anywhere in the word. > > > > > > > > >> . for eg if hello is given, result should be hellolleh > > > > > > > > >> -- > > > > > > > >> 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. > > > > > > > > > -- > > > > > > > > Saurabh Singh > > > > > > > > B.Tech (Computer Science) > > > > > > > > MNNIT ALLAHABAD > > > > > > > > > -- > > > > > > > > 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. > > > > > > > > -- > > > > > > > Mohit kumar lal > > > > > > > rit2009014 > > > > > > > IIIT ALLAHABAD > > > > > > > contact@9454681805 > > > > > > > [email protected] > > > > > > > [email protected] > > > > > > > [email protected]http://profile.iiita.ac.in/rit2009014-Hidequotedtext- > > > > > > > - Show quoted text -- Hide quoted text - > > > > - Show quoted text - -- 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.
