word ladder en python

Question

J'essaye de créer un programme de ladder de mot en python. Je voudrais générer des mots similaires à un mot donné. En C++ ou java, je passerais par chaque index valide dans la chaîne d'origine, et le remplacer par chaque lettre dans l'alphabet anglais, et voir si le résultat est un mot valide. par exemple (pseudocode)

for (int i = 0; i < word.length(); i++) { 
    for (every character c in the alphabet) { 
    change the letter of word at index i to be c. 
    if the result is a valid word, store it in a list of similar words 
    } 
} 

.

Cependant, cela ne semble pas être une façon très "python" de faire les choses. Comment pourrais-je aborder ce problème en python?

Answer 1

Un générateur de mots similaires (en prenant un prédicat, par exemple un argument de fonction qui renvoie true ou false, pour vérifier si un mot est valide) semble une première étape raisonnable:

import string 

def allsimilar(word, valid): 
    wl = list(word) 
    for i, c in enumerate(wl): 
    for x in string.ascii_lowercase: 
     if x == c: continue 
     wl[i] = x 
     nw = ''.join(wl) 
     if valid(nw): yield nw 
    wl[i] = c 

Si vous voulez la liste , list(allsimilar(word, valid)) va bien sûr le construire pour vous.

Sinon, vous pouvez omettre wl et construire le nouveau mot directement

nw = word[:i] + x + word[i+1:] 

mais, sans avoir chronométré avec soin, je pense que cela pourrait être plus lent.

Une petite optimisation possible serait aussi import array puis utiliser

wl = array.array('c', word) 

au lieu de list(word).