informatique (tronc commun des prépas scientifiques) · Chapitre 13 · Exercice de TD
L'échelle des mots
Parcours de graphes · niveau 3 (difficile)
Énoncé
Relier un mot de départ à un mot cible (ex: rame à cage) en changeant une unique lettre à chaque étape, tous les intermédiaires devant figurer dans un dictionnaire donné.
Corrigé
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