Mindestanzahl von Zeichen, die in eine Zeichenfolge eingefügt werden, um sie in Palindrom zu konvertieren

Question

Ich muss die minimale Anzahl von Einfügungen finden, die benötigt werden, um eine Zeichenfolge in ein Palindrom umzuwandeln. Hinweis: Die Einfügungen können an jedem Ort, am Ende oder innerhalb erfolgen. Wenn es nur am Ende war, haben wir eine Frage here.

So fand ich heraus, dass dies in O(N**2) Zeit durch diesen einfachen Trick getan werden kann:

1. Lassen Sie die Zeichenfolge s1. Dreh es um. Sei es s2. Angenommen, die Länge ist l.
2. Finden Sie nun die längste gemeinsame Subsequenz von s1 und s2. Lass seine Länge x sein.
3. Die Antwort ist l-x.

Zum Beispiel angenommen s1 = abcda. Daher s2 = adcba. Länge ist 5. Längste gemeinsame Teilfolge ist aba der Länge 3. So ist die minimale Anzahl der Einfügungen 5-3 = 2, die die tatsächliche Antwort ist, mit der resultierenden Zeichenfolge - adcbcda.

Allerdings kann ich die Logik dahinter nicht verstehen. Kann mir jemand erklären, warum es funktioniert?

Und, gibt es eine O(N) Lösung dafür?

Answer 1

Ich weiß nicht, ob es eine O(N) Lösung gibt, aber durch den Vergleich mit dem Rückwärts finden Sie eine Teilfolge, die ein Palindrom ist. Dann haben Sie l-x Buchstaben, die nicht gepaart sind. (Sie können das Paar eines Buchstabens als Reflexion betrachten, wenn Sie einen Spiegel in der Mitte des Wortes haben. Zum Beispiel: ab | ba) Später vervollständigen Sie das Bild durch Einfügen.

Nun, erstens, wie finden wir eine (maximale) Teilfolge, die zwei Strings gemeinsam ist? Es gibt einen Polynom-Algorithmus für die Suche nach es hier sehen https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Wenn wir versuchen, die längste gemeinsame Teilfolge (LCS) zwischen s1 und s2 (Rückwärts von s1) finden wir tatsächlich LCS zwischen der ersten Hälfte von s1 finden und ersten halb s2, auch zweite Hälfte von s1 und zweite Hälfte von s2. Angenommen

s1 = abcddzac

so s2 = cazddcba. Hier können wir es als Vergleich von abcd mit cazd (erste Hälfte) plus Vergleich von dzac mit dcba (zweite Hälfte) sehen. Wir können sehen, dass beide Vergleiche die gleichen sind, außer dass sie umgekehrt sind, so dass ihre Verkettung Palindrom sein muss, so dass lcs von s1 und s2 Palindrom sein muss.

Sobald wir die lcs (ad|da) haben, die die Länge 4 hat, haben wir 4 weitere Buchstaben, die die Symmetrie (b, c, z, c) brechen. Dann fügen wir für jeden von ihnen einen Buchstaben ein, um eine Symmetrie, d. H. Ein Palindrom, zu erzeugen.Wir setzten unseren Mittelpunkt als Mittelpunkt des LCS und bedenken, dass wir s1 in zwei von diesem Mittelpunkt zu brechen, so dass wir

s1 = a bc d|d z a c haben und wir brechen es wie ein Stock in zwei von d | d und wir am Ende mit:
d z a c
d cb a

jetzt einfach wir zwischen den Buchstaben des LCS füllen, so dass sie gleich sind. In unserem Fall sind folgende Schritte erforderlich:

d z a c
d cb a

d z a c
d ZCB a

d zc a c
d ZCB a

d ZCB a c
d ZCB a

d ZCB a c
d ZCB a c


Jetzt unbreak wir es an der gleichen Stelle, und wir haben
c a bcz dd ZCB a c Das ist ein Palindrom.

Hinweis: CDCD ist auch ein LDC, aber das ändert nicht die Anzahl der Schritte.