Suchen einer minimalen Zeichenfolge, die einige Bedingungen erfüllt

Question

Kürzlich wurde ich während eines Interviews das folgende Problem gestellt.

Bei einer Saite S muss ich eine andere Saite S2 finden, so dass S2 eine Teilfolge von S ist und auch S eine Teilfolge von S2 + reverse (S2) ist. Hier bedeutet '+' eine Verkettung. Ich muss die minimale mögliche Länge von S2 für gegebene S. ausgeben.

Mir wurde gesagt, dass dies ein dynamisches Programmierproblem ist, jedoch konnte ich es nicht lösen. Kann mir jemand bei diesem Problem helfen?

Bearbeiten-

Gibt es eine Möglichkeit, dies in O zu tun (N) oder weniger.

Answer 1

Jedes Zeichen von S kann in S2 enthalten sein oder nicht. Damit können wir Rekursion konstruieren, die zwei Fälle versucht:

• erste Zeichen S für Deckel verwendet wird,
• erste Zeichen S nicht für Deckel verwendet wird, ist,

und berechnen mindestens diese zwei Abdeckungen. Um dies zu implementieren, ist es ausreichend zu verfolgen, wie viel von S mit der bereits gewählten S2 + Reverse (S2) bedeckt ist.

Es gibt Optimierungen, bei denen wir wissen, welches Ergebnis (gefundene Deckung, kann keine Deckung haben), und es ist nicht erforderlich, das erste Zeichen für Deckung zu nehmen, wenn es etwas nicht abdecken wird.

Einfache Python-Implementierung:

cache = {} 

def S2(S, to_cover): 
    if not to_cover: # Covered 
     return '' 
    if not S:   # Not covered 
     return None 
    if len(to_cover) > 2*len(S): # Can't cover 
     return None 
    key = (S, to_cover) 
    if key not in cache: 
     without_char = S2(S[1:], to_cover)  # Calculate with first character skipped 
     cache[key] = without_char 
     _f = to_cover[0] == S[0] 
     _l = to_cover[-1] == S[0] 
     if _f or _l: 
      # Calculate with first character used 
      with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)]) 
      if with_char is not None: 
       with_char = S[0] + with_char # Append char to result 
       if without_char is None or len(with_char) <= len(without_char): 
        cache[key] = with_char 
    return cache[key] 

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132' 
c = S2(s, s) 
print len(s), s 
print len(c), c 

Answer 2

Lassen Sie uns sagen, dass S2 ist "apple". Dann können wir diese Annahme machen:

S2 + reverseS2> = S> = S2
"appleelppa"> = S> = "apple"

So das gegebene S wird etwas umfassen, das "Apfel" zu nicht mehr als "appleelppe" einschließt. Es könnte "Appleel" oder "Appleelpp" sein.

String S ="locomotiffitomoc"; 
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank 
String S2 = ""; 
for (int a=0; a<S.length(); a++) { 
    try { 
     int b = 0; 
     while (S.charAt(a - b) == S.charAt(a + b + 1)) 
      b++; 
     // if this for loop breaks that means that there is a character that doesn't match the rule 
     // if for loop doesn't break but throws an exception we found it. 
    } catch (Exception e) { 
     // if StringOutOfBoundsException is thrown this means end of the string. 
     // you can check this manually of course. 
     S2 = S.substring(0,a+1); 
     break; 
    } 
} 
System.out.println(S2); // will print out "locomotif" 

Herzlichen Glückwunsch, Sie haben das Minimum S2 gefunden.

Answer 3

Es gibt 2 wichtige Aspekte in diesem Problem.

1. Da wir S als Teil von S2 + reverse (S2) benötigen, sollten S2 haben atleast n/2 der Länge.
2. Nach Verkettung von S2 und rückwärts (S2), gibt es ein Muster, bei dem die Alphabete wie

So ist die Lösung wiederholt von der Mitte von S zu prüfen, von S zu beenden für irgendwelche aufeinanderfolgenden Elemente.Wenn Sie einen finden, überprüfen Sie die Elemente auf jeder Seite wie gezeigt.

Nun, wenn Sie bis zum Ende des Strings zu erreichen sind in der Lage, dann ist die minimale Anzahl von Elementen (Ergebnis) ist der Abstand vom Beginn bis zu dem Punkt, wo man aufeinander folgende Elemente zu finden. In diesem Beispiel ist es c. 3.

Wir wissen, dass dies nicht immer passieren kann. Möglicherweise können Sie keine aufeinanderfolgenden Elemente in der Mitte finden. Sagen wir, die aufeinanderfolgenden Elemente sind nach dem Zentrum, dann können wir den gleichen Test machen.

Haupt String

Substring

verkettete Zeichenfolge

kommt jetzt t Er hat große Zweifel. Warum betrachten wir nur die linke Seite von der Mitte aus? Die Antwort ist einfach, die verkettete Zeichenfolge wird durch S + reverse (S) erzeugt. Daher sind wir sicher, dass das letzte Element in der Teilzeichenfolge in der verketteten Zeichenfolge aufeinanderfolgen wird. Es gibt keine Möglichkeit, dass eine Wiederholung in der ersten Hälfte der Hauptsaite zu einem besseren Ergebnis führen kann, da wir zumindest die n Alphabete in der letzten verketteten Zeichenfolge haben sollten Suche nach aufeinanderfolgenden Alphabeten geben ein Maximum von O (n) Die nun iterative Überprüfung von Elementen auf beiden Seiten kann eine Worst-Case-Komplexität von O (n) ergeben. d. h. maximale n/2-Vergleiche. Wir können viele Male bei der zweiten Überprüfung versagen, so dass wir eine multiplikative Beziehung zwischen den Komplexitäten haben, d. H. O (n * n).

Ich glaube, das ist eine richtige Lösung und hat noch keine Lücke gefunden.