Convertit une chaîne de palindrome chaîne avec un minimum d'insertions

Afin de trouver le nombre minimal d'insertions nécessaires pour convertir une chaîne donnée(s) à palindrome je trouve la plus longue sous-suite commune de la chaîne(lcs_string) et son inverse. Par conséquent, le nombre d'insertions est de longueur(s) - longueur(lcs_string)

Quelle méthode doit être employée pour trouver l'équivalent palindrome de la chaîne sur le fait de savoir le nombre d'insertions?

Par exemple :

1) azbzczdzez

Nombre d'insertions requis : 5
Palindrome chaîne : azbzcezdzeczbza

Bien que plusieurs palindrome chaînes peuvent exister pour la même chaîne, mais je veux trouver un seul palindrome?

OriginalL'auteur whitepearl | 2012-05-23

  1. 12

    Laisser S[i, j] représente une sous-chaîne de la chaîne de S à partir de l'indice de i et se terminant à l'indice de j (tous deux inclus) et c[i, j] être la solution optimale pour S[i, j].

    Évidemment, c[i, j] = 0 if i >= j.

    En général, nous avons la récurrence:

    Convertit une chaîne de palindrome chaîne avec un minimum d'insertions

    OriginalL'auteur Ravi Gupta

  2. 2

    D'élaborer sur VenomFangs réponse, il y a une dynamique simple solution de programmation de celui-ci. Notez que je suis en supposant que la seule opération autorisée ici est l'insertion de caractères (pas de suppression, mises à jour). Soit S une chaîne de n caractères. Le simple récursivité de la fonction P est la suivante:

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

    P[i..j] 

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

    Si vous souhaitez plus d'explication sur pourquoi cela est vrai, poster un commentaire et je me ferais un plaisir de vous l'expliquer (bien que son très facile à voir avec un peu de réflexion). Ceci, en passant, est l'exact opposé de la CL de la fonction que vous utilisez, donc de valider que votre solution est en fait optimale. Bien sûr, sa filiale possible que j'ai raté, si oui, quelqu'un faites moi savoir!

    Edit: pour prendre en compte le palindrome lui-même, cela peut être facilement fait comme suit:
    Comme indiqué ci-dessus, P[1..n] serait vous donner le nombre d'insertions nécessaires pour faire de cette chaîne un palindrome. Une fois le au-dessus de tableau à deux dimensions est construit, voici comment vous trouvez le palindrome:

    Démarrer avec i=1, j=n. Maintenant,
    sortie de chaîne = "";

    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

    N'a que faire de mieux lire?

    Merci @kyun. Mais j'ai réussi a trouvé le nombre d'insertions d'être faite. J'ai précisé que j'ai besoin de trouver le palindrome chaîne formée après les insertions? Pouvez-vous me donner une solution optimale? En vous remerciant à l'avance.
    Édité maintenant, est-ce qu'aider?

    OriginalL'auteur kyun

  3. 0

    La solution semble être d'une programmation dynamique de la solution.

    Vous pouvez être en mesure de trouver votre réponse dans le post suivant: Comment puis-je calculer le nombre de caractères nécessaires pour transformer une chaîne en un palindrome?

    OriginalL'auteur James Oravec

  4. -1

    PHP Solution de 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 );

    OriginalL'auteur Vishnu Agarwal

  5. -2

    Simple. Voir ci-dessous 🙂

            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);
    cette solution ne vous donnera pas de droit de réponse dans la plupart des cas. Essayez OROP , 1 seul caractère est nécessaire, c'est à dire P au début, mais votre solution sera de donner la réponse 2.

    OriginalL'auteur Rohan Arora