Konwertuj ciąg na łańcuch palindrowy z minimalnymi wstawkami

Question

Aby znaleźć minimalną liczbę wstawień potrzebnych do przekonwertowania danego ciągu (ów) na palindrom, znajduję najdłuższy wspólny podciąg ciągu (lcs_string) i jego odwrotność. Dlatego liczba wstawień, które należy wprowadzić, to długość (s) - długość (lcs_string)

Jaką metodę należy zastosować, aby znaleźć równoważny ciąg palindromów na temat liczby wstawek, które należy wprowadzić?

Na przykład:

1) azbzczdzez

Ilość wstawkami Wymagane: 5 Palindrome smyczkowych: azbzcezdzeczbza

Mimo wielu ciągów palindromowych mogą istnieć w tym samym ciąg ale chcę znaleźć tylko jeden palindrom?

Answer 1

Niech S[i, j] oznacza podnapis sznurka S rozpoczynając od indeksu i i kończący się (zarówno wskaźnik j włącznie) i c[i, j] optymalnym rozwiązaniem dla S[i, j].

Oczywiście, c[i, j] = 0 if i >= j.

Generalnie mamy nawrót:

Answer 2

Rozwiązanie wygląda na dynamiczne rozwiązanie programistyczne.

Możesz być w stanie znaleźć odpowiedzi na następujące stanowisko: How can I compute the number of characters required to turn a string into a palindrome?

Answer 3

Aby rozwinąć VenomFangs odpowiedzieć, jest proste rozwiązanie dynamicznego programowania do tego. Zauważ, że zakładam, że jedyną operacją dozwoloną tutaj jest wstawianie znaków (bez usuwania, aktualizacji). Niech S będzie ciągiem znaków n. Prosta funkcja rekursji P na to:

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

P [i..j]

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

Jeśli chcesz więcej wyjaśnień, dlaczego to prawda, skomentować i ja bądź szczęśliwy, aby wyjaśnić (choć jest to dość łatwe do zrozumienia przy odrobinie myśli). To, nawiasem mówiąc, jest dokładnym przeciwieństwem funkcji LCS, której używasz, potwierdzając tym samym, że twoje rozwiązanie jest w rzeczywistości optymalne. Oczywiście, że jest to całkowicie możliwe, spartaczyłem, jeśli tak, to ktoś mi dał znać!

Edit: W celu uwzględnienia samego palindrom, można to łatwo zrobić w następujący sposób: Jak stwierdzono powyżej, P [1..n] nie daje liczbę wstawek wymagane, aby ten ciąg palindrom. Po zbudowaniu powyższej dwuwymiarowej tablicy, oto jak znaleźć palindrom:

Zacznij za pomocą i = 1, j = n. Teraz, ciąg znaków = "";

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 

Czy to sprawia, że ​​lepsze czytanie?

Answer 4

proste.Patrz poniżej :)

 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 Rozwiązanie 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);