L'échelle des mots

On modélise le problème par un graphe implicite où les sommets sont les mots et une arête relie deux mots s'ils diffèrent d'une seule lettre. La recherche du chemin le plus court s'effectue avec un BFS.

def different_d_une_lettre(u: str, v: str) -> bool:
    return len(u) == len(v) and sum(1 for a, b in zip(u, v) if a != b) == 1

def echelle_mots(lexique: list, source: str, cible: str):
    G = {m: [v for v in lexique if different_d_une_lettre(m, v)] for m in lexique}
    dist, pere = {source: 0}, {}
    file = deque([source])
    while file:
        s = file.popleft()
        if s == cible:
            break
        for v in G[s]:
            if v not in dist:
                dist[v] = dist[s] + 1
                pere[v] = s
                file.append(v)
    if cible not in dist:
        return None
    # Reconstruction
    c = [cible]
    while c[-1] != source:
        c.append(pere[c[-1]])
    c.reverse()
    return c