Transformation de mots à coût le plus court

Question

J'essaie de résoudre la question suivante.

Vous obtenez un mot de départ, un dictionnaire et un mot de fin. Vous pouvez effectuer 4 opérations.

1. Ajouter une lettre à toute position
2. Supprimer une lettre à toute position
3. Remplacer une lettre à toute position
4. Prenez mot de anagram (chat peut être changé pour agir).

Tous les coûts de ces opérations peuvent être différents et sont donnés aussi. Contrainte: toutes les lettres intermédiaires avec le mot de départ et le mot de fin doivent être présents dans le dictionnaire. Trouvez le coût minimum possible pour y parvenir.

S'il n'y a aucun moyen de retourner -1;

Des idées s'il vous plaît?

Answer 1

Je pense que vous devriez me donner plus de détails sur les contraintes (comme la longueur maximale des mots ou le nombre maximum de mots dans le dictionnaire).

Mais je vais vous dire une solution pour résoudre ce problème.

D'abord, vous pouvez créer un graphique. Chaque nœud est un mot que vous pouvez faire (dans le dictionnaire) et le bord est l'opération que vous pouvez faire.

Chaque arête a un poids donné par l'entrée. Ensuite, vous devez enregistrer la distance entre le mot de départ et tous les autres mots du dictionnaire. En C++, vous pouvez déclarer map<string, int>.

La clé de cette carte est la chaîne de noeud et la valeur de cette carte est la distance du mot initial. Ensuite, vous pouvez utiliser des algorithmes de distance la plus courte comme dijkstra. Le point de départ est le mot initial et le point d'arrivée est un mot que l'on veut faire. Parce que Dijkstra est l'algorithme le plus rapide avec un point de départ habituel, je l'utiliserai si j'étais vous.

Ensuite, calculons la complexité temporelle.

Disons que la longueur maximale de chaque mot est S et le nombre maximum de mots dans le dictionnaire est N.

Dans chaque opération, il faut O (S) si vous changez de position de certains caractères ou ajouter ou supprimer un personnage dans une certaine position sauf le dos du mot et O (1) si vous changez simplement un caractère. Quoi qu'il en soit, la complexité totale du temps est O (SNlgN) cuz le nombre maximum de nœuds dans notre graphe est le nombre maximum de mots dans le dictionnaire parce qu'il y a des mots dans le dictionnaire que nous pouvons faire avec le mot que nous avons maintenant, alors on ne peut plus faire de bord depuis le noeud courant.

Et le nombre maximum d'arêtes est O (N) cuz nous pouvons faire 4 arêtes dans chaque nœud au maximum. Donc, si vous connaissez la complexité temporelle de Dijkstra avec tas, c'est simple.

Answer 2

Je pense que vous devriez me donner plus de détails sur la contrainte (comme la longueur maximale des mots ou le nombre maximum de mots dans le dictionnaire). Mais je vais vous dire quelques façons de résoudre ce problème. Tout d'abord, vous pouvez créer un graphique. Chaque nœud est un mot que vous pouvez faire (dans le dictionnaire) et le bord est l'opération que vous pouvez faire. Chaque arête a un poids qui est donné par l'entrée. En C++, vous pouvez déclarer la carte <string, int>. La clé de cette carte est la chaîne du noeud et la valeur de cette carte est la distance du mot initial. Ensuite, vous pouvez utiliser des algorithmes de distance la plus courte comme dijkstra. Parce que Dijkstra est l'algorithme le plus rapide avec un point de départ habituel, je l'utiliserai si j'étais vous. Ensuite, calculons la complexité du temps. Disons que la longueur maximale de chaque mot est S et que le nombre maximal de mots dans le dictionnaire est N. Dans chaque opération, il faut O (S) si vous pouvez changer la position de certains caractères ou ajouter ou supprimer un caractère dans une position autre que du mot