Konvertieren von Zeichenfolge in Palindrom-Zeichenfolge mit minimalen Einfügungen

Question

Um die minimale Anzahl von Einfügungen zu finden, die zum Konvertieren einer gegebenen Zeichenfolge (n) zu Palindrom erforderlich ist, finde ich die längste gemeinsame Untersequenz der Zeichenfolge (lcs_string) und umgekehrt. Daher ist die Anzahl der einzufügenden Einfügungen Länge (n) - Länge (lcs_string)

Welche Methode sollte verwendet werden, um die äquivalente Palindrom-Zeichenfolge zu finden, wenn man die Anzahl der einzuführenden Einfügungen kennt?

Zum Beispiel:

1) azbzczdzez

Anzahl der Einfügungen erforderlich: 5 Palindrome string: azbzcezdzeczbza

Obwohl mehrere Palindrom-Strings für die gleiche Zeichenfolge vorhanden sind, aber ich möchte nur finden, Palindrom?

Answer 1

S[i, j] Lassen Sie stellt eine Unterkette von Zeichenkette S aus dem Index beginnend i und endend bei Index j (beide inklusive) und c[i, j] die optimale Lösung für S[i, j] sein.

Offensichtlich c[i, j] = 0 if i >= j.

Im Allgemeinen haben wir die Wiederholung:

Answer 2

Die Lösung scheint eine dynamische Programmierlösung zu sein.

Sie können eventuell Ihre Antwort in dem folgenden Beitrag finden: How can I compute the number of characters required to turn a string into a palindrome?

Answer 3

Um näher auf VenomFangs beantworten, ist es eine einfache dynamische Programmierlösung zu diesem. Beachten Sie, dass ich annahm, dass hier nur Zeichen eingefügt werden dürfen (keine Löschung, Updates). Sei S eine Folge von n Zeichen. Die einfache Rekursion Funktion P hierfür ist:

= P [i+1 .. j-1], if S[i] = S[j] 

P [i..j]

= min (P[i..j-1], P[i+1..j]) + 1, 

Wenn Sie mehr Erklärung möchten, warum dies wahr ist, schreiben Sie einen Kommentar und ich würde sei froh zu erklären (obwohl es mit ein wenig Nachdenken ziemlich leicht zu sehen ist). Dies ist übrigens das genaue Gegenteil der von Ihnen verwendeten LCS-Funktion und bestätigt somit, dass Ihre Lösung tatsächlich optimal ist. Natürlich ist es völlig möglich, dass ich mich verpfuscht habe, wenn ja, jemand lässt es mich wissen!

Edit: Um sich für das Palindrom-Konto selbst, kann dies leicht geschehen wie folgt: Wie oben erwähnt, P [1..n] würde Ihnen die Anzahl von Einfügungen erforderlich, um diese Zeichenfolge ein Palindrom zu machen. Sobald das obige zweidimensionale Array aufgebaut ist, folgt das Palindrom:

Beginnen Sie mit i = 1, j = n. Jetzt, string output = "";

while(i < j) 
{ 
    if (P[i][j] == P[i+1][j-1]) //this happens if no insertions were made at this point 
    { 
     output = output + S[i]; 
     i++; 
     j--; 
    } 
    else 
    if (P[i][j] == P[i+1][j]) // 
    { 
     output = output + S[i]; 
     i++; 
    } 
    else 
    { 
     output = S[j] + output; 
     j--; 
    } 
} 
cout<<output<<reverse(output); 
//You may have to be careful about odd sized palindromes here, 
// I haven't accounted for that, it just needs one simple check 

Macht das besseres Lesen?

Answer 4

Einfach.Siehe unten :)

 String pattern = "abcdefghgf"; 
     boolean isPalindrome = false; 
     int i=0,j=pattern.length()-1; 
     int mismatchCounter = 0; 

     while(i<=j) 
     { 
      //reverse matching 
      if(pattern.charAt(i)== pattern.charAt(j)) 
       { 
        i++; j--; 
        isPalindrome = true; 
        continue; 
       } 

      else if(pattern.charAt(i)!= pattern.charAt(j)) 
       { 
        i++; 
        mismatchCounter++; 
       } 


     } 
     System.out.println("The pattern string is :"+pattern); 
     System.out.println("Minimum number of characters required to make this string a palidnrome : "+mismatchCounter); 

Answer 5

PHP-Lösung von O (n)

function insertNode(&$arr, $idx, $val) { 
    $arr = array_merge(array_slice($arr, 0, $idx), array($val), array_slice($arr, $idx)); 
} 
function createPalindrome($arr, $s, $e) { 
    $i = 0; 
    while(true) { 
     if($s >= $e) { 
      break; 
     } else if($arr[$s] == $arr[$e]) { 
      $s++; $e--; // shrink the queue from both sides 
      continue; 
     } else { 
      insertNode($arr, $s, $arr[$e]); 
      $s++; 
     } 
    } 
    echo implode("", $arr); 
} 
$arr = array('b', 'e', 'a', 'a', 'c', 'd', 'a', 'r', 'e'); 
echo createPalindrome ($arr, 0, count ($arr) - 1);