Converti stringa in stringa palindrome con inserimenti minimi

Question

Per trovare il numero minimo di inserimenti necessari per convertire una stringa specifica in palindrome, trovo la sottosequenza più lunga comune della stringa (lcs_string) e il suo contrario. Pertanto il numero di inserimenti da effettuare è lunghezza (s) - lunghezza (lcs_string)

Quale metodo deve essere impiegato per trovare la stringa palindromo equivalente alla conoscenza del numero di inserimenti da realizzare?

Ad esempio:

1) azbzczdzez

Numero di inserimenti richiesti: 5 stringa Palindrome: azbzcezdzeczbza

Anche se possono esistere più stringhe palindrome per la stessa stringa, ma voglio trovare un solo palindromo?

Answer 1

Sia S[i, j] rappresenta una sotto-stringa di stringa S partire dall'indice i e termina in corrispondenza dell'indice j (entrambi inclusi) e c[i, j] essere la soluzione ottimale per S[i, j].

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

In generale, abbiamo la ricorrenza:

Answer 2

La soluzione sembra essere una soluzione di programmazione dinamica.

Si può essere in grado di trovare la risposta nel seguente post: How can I compute the number of characters required to turn a string into a palindrome?

Answer 3

di approfondire VenomFangs rispondere, c'è una soluzione semplice programmazione dinamica a questo. Si noti che sto assumendo che l'unica operazione consentita qui sia l'inserimento di caratteri (nessuna eliminazione, aggiornamenti). Sia S una stringa di n caratteri. La semplice funzione ricorsione P per questo è:

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

P [i..j]

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

Se vuoi maggiori spiegazioni sul motivo per cui questo è vero, inviare un commento e mi piacerebbe essere felice di spiegare (anche se è piuttosto facile da vedere con un pensierino). Questo, a proposito, è l'esatto opposto della funzione LCS che usi, quindi convalida che la tua soluzione sia effettivamente ottimale. Certo che è del tutto possibile, ho commesso un pasticcio, se così fosse, qualcuno me lo faccia sapere!

Modifica: Per spiegare il palindromo stesso, questo può essere fatto facilmente come segue: Come detto sopra, P [1..n] darebbe il numero di inserzioni necessari per rendere questa stringa un palindromo. Una volta creato l'array bidimensionale sopra, ecco come si trova il palindrome:

Inizia con i = 1, j = n. Ora, 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 

Questo rende la lettura migliore?

Answer 4

semplice.Vedi sotto :)

 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 Soluzione di 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);