@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 <topcode...@gmail.com> 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 <sourabhd2...@gmail.com> wrote:
>
>
>
>
>
>
>
> > Correction:
>
> > for NAN :
> > N(IT)A + TI + N = NITATIN
>
> > On Dec 15, 11:33 am, Lucifer <sourabhd2...@gmail.com> 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 <topcode...@gmail.com> 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 <sourabhd2...@gmail.com> 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 <kumarmohit...@gmail.com> 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
> > > > > > <saurab...@gmail.com> wrote:
> > > > > > > Find the LCS of string with its reverse....
>
> > > > > > > On Wed, Dec 14, 2011 at 8:33 PM, top coder <topcode...@gmail.com>
> > > > > > > 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 algogeeks@googlegroups.com.
> > > > > > >> To unsubscribe from this group, send email to
> > > > > > >> algogeeks+unsubscr...@googlegroups.com.
> > > > > > >> 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 algogeeks@googlegroups.com.
> > > > > > > To unsubscribe from this group, send email to
> > > > > > > algogeeks+unsubscr...@googlegroups.com.
> > > > > > > For more options, visit this group at
> > > > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > > > > --
> > > > > > Mohit kumar lal
> > > > > > rit2009014
> > > > > > IIIT ALLAHABAD
> > > > > > contact@9454681805
> > > > > > kumarmohit...@gmail.com
> > > > > > mohitkumar...@yahoo.com
> > > > > > rit2009...@iiita.ac.inhttp://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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
