Étant donné un mot, de le convertir en un palindrome avec un minimum de plus de lettres d' [fermé]

Question

Il est difficile de dire ce qui est demandé ici.Cette question est ambiguë, imprécise, incomplète, trop large, ou de la rhétorique et ne peut pas être raisonnablement répondu dans sa forme actuelle.Pour aider à clarifier cette question, de sorte qu'il peut être rouvert, visitez le centre d'aide.

Fermé Il y a 7 ans.

Voici une très intéressante question d'entrevue:

Étant donné un mot, ajouter le plus petit nombre de lettres pour le convertir en un palindrome.

Par exemple, si "bonjour" est la chaîne de caractères donnée, le résultat doit être "hellolleh." Si "coco" est donné, le résultat doit être "cococ."

Une approche à laquelle je pense est à ajouter à l'inverse de la chaîne à la fin de la chaîne d'origine, puis essayez d'éliminer les caractères supplémentaires à partir de la fin.Cependant, je ne peux pas comprendre comment le faire efficacement.Quelqu'un aurait-il des idées?

Answer 1

Faire d'abord une fonction pour tester la chaîne pour Palindrome-Ness, gardant à l'esprit que "A" et "AA" sont des palindromes.Ce sont des palindromes, non ???

Si l'entrée est un palindrome, renvoyez-la (0 caractères à ajouter) Boucle de x [longueur] bas sur x [1] Vérification si le sous-ensemble de la chaîne x [i] .. x [longueur] est un palindrome, pour trouver le palindrome le plus long.

Prenez la sous-chaîne de la chaîne d'entrée avant le palindrome le plus long, l'inversant et l'ajoutez-la à la fin devrait rendre le Palindrome le plus court via Ajout.

coco=> c + oco=> c + oco + c

mmMeep=> mmmee + p=> mmmee + p + eemmm

Answer 2

D'accord!Voici ma deuxième tentative.

L'idée est que nous voulons savoir combien de caractères à la fin de la chaîne peut être réutilisé lors de l'ajout des caractères supplémentaires pour compléter le palindrome.Pour ce faire, nous allons utiliser une modification de l'KMP chaîne de caractères correspondant à l'algorithme.À l'aide de KMP, nous sommes la recherche de la chaîne d'origine pour son inverse.Une fois que nous obtenons à la fin de la chaîne, nous aurons autant de match que possible entre l'inverse de la chaîne et de la chaîne d'origine qui se produit à la fin de la chaîne.Par exemple:

HELLO
    O

1010
 010

3202
 202

1001
1001

À ce stade, KMP, normalement, dirais "aucun match", à moins que la chaîne d'origine est un palindrome.Cependant, puisque nous savons combien l'inverse de la chaîne a été trouvée, nous pouvons, au lieu juste de savoir combien de caractères sont toujours portées disparues et puis tack à la fin de la chaîne.Dans le premier cas, il nous manque LLEH.Dans le second cas, il nous manque 1.Dans la troisième, il nous manque 3.Dans le dernier cas, nous ne sommes pas en manque quoi que ce soit, depuis la première chaîne est un palindrome.

Le moteur d'exécution de cet algorithme est la durée d'un standard KMP la recherche, ainsi que le temps nécessaire à l'inverse de la chaîne:O(n) + O(n) = O(n).

Donc maintenant pour débattre de la justesse.Cela va exiger un certain effort.Examiner la réponse optimale:

   | original string | | extra characters |

Supposons que nous sommes à la lecture de cet arrière à partir de la fin, ce qui signifie que nous allons lire au moins l'inverse de la chaîne d'origine.Une partie de cette chaîne inversée s'étend vers l'arrière dans le corps de la chaîne d'origine lui-même.En effet, afin de minimiser le nombre de caractères ajoutés, ce qui a le plus grand nombre possible de caractères qui se termine en arrière dans la chaîne elle-même.Nous pouvons le voir ici:

   | original string | | extra characters |
           | overlap |

Maintenant, ce qui se passe dans notre KMP étape?Ainsi, lors de la recherche de l'inverse de la chaîne à l'intérieur de lui-même, KMP va garder le plus longtemps d'un match que possible à toutes les fois qu'il fonctionne à travers la chaîne.Cela signifie que lorsque le KMP hits de la fin de la chaîne, correspondant à la partie, il assure que ce sera la plus longue possible, depuis KMP ne se déplace que le point de départ du candidat match à suivre sur un échec.Par conséquent, nous avons la plus longue possible, se chevauchent, de sorte que nous allons obtenir le plus possible le nombre de caractères requis à la fin.

Je ne suis pas sûr à 100% que cela fonctionne, mais il semble que cela fonctionne dans tous les cas, je peut jeter à elle.La preuve de correction semble raisonnable, mais c'est un peu attrayante parce que le formel KMP base de la preuve serait sans doute un peu délicat.

Espérons que cette aide!

Answer 3

Pour répondre, je prendrais cette approche naïve:

1. Quand nous avons besoin de 0 caractères?Quand la chaîne c'est un palindrome
2. Quand nous avons besoin d'un personnage?Lorsque si la première chaîne de caractères est un palindrome
3. Quand nous avons besoin de 2 caractères?Lorsque sauf les 2 caractères de démarrage, la chaîne est un palindrome
4. etc etc ...

   donc un algorithme pourrait être

     for index from 1 to length
      if string.right(index) is palindrome
       return string + reverse(string.left(index))
      end
     next
   

   éditer

   Je ne suis pas beaucoup un gars python, mais une implémentation simple d'esprit du code pseudo ci-dessus pourrait être

   >>> def rev(s): return s[::-1]
   ... 
   >>> def pal(s): return s==rev(s)
   ... 
   >>> def mpal(s):
   ...  for i in range(0,len(s)):
   ...   if pal(s[i:]): return s+rev(s[:i])
   ... 
   >>> mpal("cdefedcba")
   'cdefedcbabcdefedc'
   >>> pal(mpal("cdefedcba"))
   True
   

Answer 4

Solution de temps linéaire simple.

Appelons notre chaîne s.

Soit F (x, p) la longueur du préfixe commun le plus long de X et P. Compute F (S [0], REV (S)), F (S [1], REV (S)),... où s [k] est le suffixe de S à partir de la position K.Évidemment, vous souhaitez choisir le minimum k tel que K + F (S [K], REV (S))= Len (s).Cela signifie que vous devez simplement ajouter K caractères à la fin.Si k est 0, la piqûre est déjà un palindrome.Si k= len (s), alors vous devez ajouter l'ensemble de l'inverse.

Nous avons besoin de calculer F (S [I], P) pour tous les [i] rapidement.C'est la partie délicate.Créer un arbre suffixe de S. Traverser l'arborescence et mettre à jour chaque nœud avec la longueur du préfixe commun le plus long avec P. Les valeurs des feuilles correspondent à F (S [I], P).