Algorithme pour transformer un mot en un autre à travers des mots valides

Question

Je suis tombé sur cette variation de edit-distance problème :

Concevez un algorithme qui transforme un mot source en un mot cible. Par exemple : de la tête à la queue, à chaque étape, vous ne pouvez remplacer qu'un seul caractère, et le mot doit être valide. On vous donne un dictionnaire.

Il s'agit clairement d'une variation de la distance d'édition mais à distance d'édition, je ne me soucie pas de savoir si le mot est valide ou non. Alors comment ajouter cette exigence à la distance d'édition ?

Answer 1

Ceci peut être modélisé comme un problème de graphe. Vous pouvez considérer les mots comme les nœuds du graphique et deux nœuds sont reliés si et seulement s'ils sont de même longueur et diffèrent par un seul caractère.

Vous pouvez prétraiter le dictionnaire et créer ce graphique, qui devrait ressembler à ceci :

   stack  jack
    |      |
    |      |
   smack  back -- pack -- pick

Vous pouvez ensuite avoir un mappage du mot au nœud représentant le mot, pour cela vous pouvez utiliser une table de hachage, une BST équilibrée en hauteur ...

Une fois que vous avez mis en place le mappage ci-dessus, il ne vous reste plus qu'à voir s'il existe un chemin entre les deux nœuds du graphe, ce qui peut facilement être fait en utilisant BFS ou DFS.

On peut donc résumer l'algorithme comme suit :

preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
 Not possible to convert
else
 n1 = get_node(w1)
 n2 = get_node(w2)

 if(path_exists(n1,n2))
   Possible and nodes in the path represent intermediary words
 else
   Not possible

Answer 2

L'approche graphique de codaddict est valable, bien qu'il faille O(n^2) temps pour construire chaque graphique, où n est le nombre de mots d'une longueur donnée. Si c'est un problème, vous pouvez construire un bk-tree beaucoup plus efficacement, ce qui permet de trouver tous les mots ayant une distance d'édition donnée (dans ce cas, 1) d'un mot cible.

Answer 3

Créez un graphe dont chaque nœud représente un mot du dictionnaire. Ajouter un bord entre deux nœuds de mots, si leurs mots correspondants sont à une distance d'édition de 1. Ensuite, le nombre minimum de transformations requises serait la longueur du plus court chemin entre le nœud source et le nœud destination.

Answer 4

Je ne pense pas que ce soit la distance d'édition.

Je pense que cela peut être fait en utilisant un graphique. Il suffit de construire un graphe à partir de votre dictionnaire, et d'essayer de naviguer en utilisant votre algorithme de traversée de graphe préféré jusqu'à la destination.

Answer 5

Il s'agit clairement d'un problème de permutation. Utiliser un graphe est exagéré. Il manque une contrainte importante dans l'énoncé du problème ; que vous ne pouvez changer chaque position qu'une seule fois . Il est donc implicite que la solution se trouve en 4 étapes. Il ne reste plus qu'à décider de la séquence des opérations de remplacement :

Opération 1 = changer "H" en "T".
Opération2 = changer "E" en "A"
Opération 3 = changer "A" en "I".
Opération4 = changer "D" en "L".

La solution, la séquence d'opérations, est une permutation de la chaîne "1234", où chaque chiffre représente la position du caractère à remplacer. Par exemple, "3124" indique que nous appliquons d'abord l'opération 3, puis l'opération 1, puis l'opération 2, puis l'opération 4. À chaque étape, si le mot résultant n'est pas dans le dictionnaire, on passe à la permutation suivante. Raisonnablement trivial. Quelqu'un veut coder ?