Word Ladder

Q: La recherche en largeur bidirectionnelle peut-elle accélérer Word Ladder ?

Oui. Lance la recherche simultanément à partir de beginWord et de endWord , en développant toujours le côté le plus petit d’un niveau, et arrête-toi lorsqu’un nouveau mot a déjà été atteint par l’autre côté. L’échelle comporte alors un mot de plus que le nombre total de changements effectués des deux côtés. Si chaque mot a environ b voisins et que l’échelle nécessite d changements, une recherche peut parcourir environ b^d mots, tandis que deux recherches qui se rejoignent au milieu en parcourent environ 2 × b^(d/2) .

DifficileGraphes File

+10

Vous recevez deux mots, beginWord et endWord, ainsi qu’une liste de mots wordList. Une chaîne est une séquence de mots qui commence par beginWord, se termine par endWord et dans laquelle une seule lettre change d’un mot au suivant. Chaque mot après beginWord doit provenir de wordList.

Renvoyez le nombre de mots de la chaîne la plus courte, en comptant les deux extrémités, ou 0 si aucune chaîne n’existe. Par exemple, cold, cord, card forment une chaîne de 3 mots. beginWord n’a pas besoin de figurer dans wordList, mais endWord doit y figurer.

Fonction

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: le premier mot de l'échelle
endWordstring: le mot que l’échelle doit atteindre
wordListstring-array: les mots dont chaque étape ultérieure doit provenir
Renvoieinteger: le nombre de mots dans la chaîne la plus courte, ou 0 s'il n'y en a aucune

Contraintes

1 ≤ beginWord.length ≤ 10
endWord et chaque mot de wordList ont la même longueur que beginWord.
1 ≤ wordList.length ≤ 5000
Tous les mots sont composés uniquement de lettres anglaises minuscules.
beginWord != endWord
Les mots de wordList sont tous différents. beginWord peut en faire partie ou non.

Exemples

Entrée: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Sortie: 4
Explication: lead et gold diffèrent par trois lettres, donc aucune échelle ne comporte moins de 4 mots, et lead, load, goad, gold en comporte exactement 4. lend et lewd ne diffèrent aussi que d’une lettre de lead, mais aucun des deux ne mène à un nouvel endroit, et bold ne peut être atteint qu’à partir de gold lui-même.

Entrée: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Sortie: 0
Explication: cat, cot, cog se rapproche de dog à une lettre près, mais dog ne figure pas dans la liste, donc aucune échelle ne peut s’y terminer.

Entrée: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Sortie: 3
Explication: ab, ad, cd et ab, cb, cd comptent tous deux 3 mots. ab figure également dans la liste, mais le début n’est compté qu’une seule fois dans les deux cas.

+14 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer l’une des séquences les plus courtes elle-même, avec les mots dans l’ordre, et pas seulement sa longueur ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Considérez les mots comme les nœuds d’un graphe, avec une arête entre deux mots qui diffèrent d’une lettre. Une échelle est alors un chemin de beginWord à endWord, et toutes les arêtes ont le même coût ; l’échelle la plus courte est donc le chemin qui comporte le moins d’arêtes. Le parcours en largeur permet de trouver exactement ce chemin. La difficulté du problème est de trouver rapidement les arêtes : comparer toutes les paires parmi 5 000 mots représente 25 millions de comparaisons, donc la meilleure solution recherche les voisins à l’aide de motifs génériques. Ci-dessous, n est le nombre de mots et L leur longueur.

Essaie chaque échelle avec une recherche en profondeur

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Commence à beginWord. À partir du mot actuel, essaie chaque mot inutilisé qui diffère d’une lettre et approfondis la recherche à partir de celui-ci. Lorsque tu atteins endWord, note la longueur de la chaîne si elle est la plus courte jusqu’à présent. Marque comme utilisés les mots du chemin actuel afin qu’une chaîne ne boucle jamais sur elle-même, et libère chaque mot lorsque tu reviens en arrière pour que d’autres chaînes puissent l’utiliser. Dès que tu as une chaîne de best mots, arrête de prolonger tout chemin qui compte déjà best-1 mots : il ne peut pas aboutir à une chaîne plus courte.

C’est correct, car l’algorithme essaie toutes les chaînes qui ne répètent jamais de mot, et une chaîne la plus courte ne répète jamais de mot : si un mot apparaissait deux fois, supprimer la partie entre ses deux occurrences produirait une chaîne plus courte.

C’est lent parce que le nombre de chaînes explose. Prends 26 mots qui ne diffèrent que par leur première lettre, aaa, baa jusqu’à zaa : chaque paire diffère d’une lettre, donc la recherche peut les parcourir dans n’importe quel ordre avant de continuer, et 26 mots peuvent être ordonnés d’environ 4 × 10^26 façons. L’élagage n’aide qu’une fois qu’une chaîne a été trouvée. Lorsque endWord est totalement inaccessible, rien n’est jamais élagué, et une liste de 34 mots dépasse déjà ce que la recherche peut traiter jusqu’au bout. La récursion peut aussi atteindre une profondeur égale à la longueur de la chaîne, qui peut compter des milliers de mots.

Algorithme

Marquez beginWord comme utilisé s’il figure dans la liste, et définissez best à 0.
Écrivez search(word, length). Si word est endWord, conservez length s’il est supérieur à best, puis retournez.
Si best n’est pas égal à 0 et que length + 1 ≥ best, retournez : ce chemin ne peut pas gagner.
Pour chaque mot non utilisé situé à une lettre de word, marquez-le comme utilisé, appelez search(next, length + 1), puis marquez-le comme non utilisé.
Appelez search(beginWord, 1) et retournez best, qui reste à 0 s’il n’existe aucune échelle.

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

Parcours en largeur, comparaison de chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La recherche en largeur explore les mots par ordre de distance. D’abord beginWord, une échelle d’un mot. Puis chaque mot qui en diffère d’une lettre, des échelles de 2 mots. Ensuite, chaque nouveau mot qui diffère d’une lettre de ceux-là, des échelles de 3 mots, et ainsi de suite. Une file d’attente conserve cet ordre : les mots en sortent dans l’ordre où ils y sont entrés, de sorte que tous les mots à la distance d en sortent avant tout mot à la distance d + 1.

C’est cet ordre qui explique pourquoi la première échelle trouvée par la recherche en largeur est la plus courte. Lorsqu’un mot est atteint pour la première fois à la distance d, tous les mots situés à une distance inférieure à d ont déjà été explorés ; si une échelle plus courte jusqu’à ce mot existait, la recherche l’aurait donc atteint plus tôt. Le même raisonnement permet de marquer un mot comme visité dès qu’il rejoint la file d’attente : sa distance est définitive, et l’atteindre à nouveau plus tard ne peut que donner une distance plus grande. Ainsi, chaque mot rejoint la file une seule fois et, dès que endWord apparaît comme voisin, sa distance est la réponse.

Cette version trouve les voisins d’un mot en le comparant à chaque mot de la liste, lettre par lettre, et en s’arrêtant à la deuxième différence. Pour chacun des jusqu’à n mots qui sortent de la file, il faut effectuer n comparaisons portant sur jusqu’à L lettres, soit O(n² × L) au total. Avec 5 000 mots et une recherche qui en visite la plupart, cela représente jusqu’à 25 millions de comparaisons de mots. Un langage compilé effectue ces opérations rapidement, mais Python nécessite plusieurs secondes pour le test le plus volumineux.

Algorithme

Si endWord ne figure pas dans wordList, renvoie 0.
Place beginWord dans une file d’attente de longueur 1. Marque-le comme visité s’il figure dans la liste.
Récupère le mot suivant et sa longueur dans la file d’attente.
Compare-le à chaque mot non visité de la liste. Pour chaque mot qui diffère d’exactement une lettre : s’il s’agit de endWord, renvoie length + 1 ; sinon, marque-le comme visité et ajoute-le avec length + 1.
Si la file d’attente est vide, endWord est inaccessible : renvoie 0.

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

Recherche en largeur avec des compartiments à caractères génériques

Intuition

Conserve le parcours en largeur et rends la recherche des voisins peu coûteuse. Deux mots sont séparés d'une seule lettre exactement lorsque le fait de masquer la même position dans les deux les rend égaux : hot et hit deviennent tous deux h*t. Donne donc à chaque mot L motifs, un par position masquée, et ajoute le mot dans un compartiment pour chaque motif. Les voisins d'un mot sont les autres mots de ses L compartiments, trouvés grâce à L recherches de hachage au lieu de parcourir toute la liste.

Voici la recherche sur le premier exemple. lead a les motifs *ead, l*ad, le*d et lea*. Le compartiment l*ad contient load et le*d contient lend et lewd, donc le niveau 2 comprend ces trois mots. À partir de load, le compartiment *oad donne goad au niveau 3 et, à partir de goad, go*d donne gold au niveau 4.

Une économie supplémentaire : lorsqu'on a parcouru le compartiment d'un mot, tous les mots qu'il contient ont été atteints, alors vide-le. Les mots suivants qui partagent le motif n'y trouveraient de toute façon rien de nouveau. Dans le test où aaa, baa jusqu'à zaa partagent *aa, ce compartiment de 26 mots est parcouru une seule fois au lieu de 26 fois. La recherche lit donc chaque entrée des compartiments parmi les n × L au plus une fois.

La construction des motifs nécessite n × L chaînes de L lettres, O(n × L²) en temps et en espace, et la recherche coûte autant : chaque mot retiré de la file construit à nouveau ses L motifs. Pour 5 000 mots de 10 lettres, cela représente environ 500 000 étapes de lettres, contre jusqu'à 250 millions pour la comparaison par paires.

Algorithme

Si endWord ne figure pas dans wordList, renvoie 0.
Pour chaque mot de la liste, ainsi que pour beginWord, ajoute le mot au compartiment correspondant à chacun de ses motifs de L.
Initialise la file avec beginWord, marque-le comme visité et définis la longueur à 1.
Traite la file niveau par niveau. Si un mot est endWord, renvoie la longueur. Sinon, pour chacun de ses motifs, ajoute tous les mots non visités de ce compartiment au niveau suivant, marque-les comme visités et vide le compartiment.
Après chaque niveau, ajoute 1 à la longueur. Si la file devient vide, renvoie 0.

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0

Pièges et cas limites

La plupart des mauvaises réponses viennent du fait qu’on ne compte pas la bonne chose ou qu’on ne respecte pas la règle concernant endWord.

Renvoyer le nombre de changements au lieu du nombre de mots. Il faut 3 changements et 4 mots pour passer de lead à gold, et la réponse est 4.
Ne pas vérifier que endWord figure dans wordList. Dans le deuxième exemple, la recherche obtient une lettre à partir de dog, mais la réponse est 0.
Utiliser une recherche en profondeur et renvoyer la première chaîne trouvée. La recherche en profondeur suit une branche aussi loin que possible, donc sa première chaîne est souvent longue.
Marquer un mot comme visité lorsqu’il quitte la file plutôt que lorsqu’il y entre. Un mot appartenant à un compartiment complet de 26 lettres peut alors entrer dans la file jusqu’à 25 fois, et la file dépasse largement n.
Laisser beginWord non marqué lorsqu’il figure également dans wordList. La recherche l’atteint alors de nouveau deux niveaux plus tard et répète le travail. Marquez-le comme visité dès le départ.
Vérifier si les mots diffèrent d’au plus une lettre. Chaque mot diffère de lui-même de zéro lettre, la condition doit donc être exactement une lettre.
Utiliser la récursion pour parcourir la chaîne. Un test caché comporte une chaîne la plus courte de 1 500 mots, suffisamment longue pour faire déborder la pile d’appels dans certains langages. BFS n’a besoin que d’une file.

Questions fréquentes4

Pourquoi la recherche en largeur trouve-t-elle la plus courte chaîne de mots ?

BFS explore les mots par étapes : d’abord le mot de départ, puis chaque mot situé à une modification de celui-ci, puis chaque mot situé à deux modifications. Un mot est atteint pour la première fois à l’étape la plus précoce qui permet de l’atteindre ; sa distance correspond donc au nombre minimal de modifications possible. Cela ne fonctionne que parce que chaque modification a le même coût. Si les étapes avaient des coûts différents, il faudrait utiliser l’algorithme de Dijkstra.

Quelle est la complexité temporelle de Word Ladder ?

Avec des compartiments à caractères génériques, la création des motifs et l’exécution de la recherche prennent un temps de O(n × L²) pour n mots de longueur L, puisque chaque mot possède L motifs de L lettres. Comparer chaque paire de mots coûte plutôt O(n² × L), et essayer toutes les chaînes avec une recherche en profondeur d’abord a un coût exponentiel.

Comment trouver les mots qui ne diffèrent que d’une lettre ?

Une méthode consiste à utiliser les compartiments avec caractères génériques ci-dessus : les mots qui partagent un motif tel que h*t sont voisins. L’autre consiste à remplacer chaque position du mot par chacune des 26 lettres et à rechercher le résultat dans un ensemble de hachage des mots. Cela coûte 26 × L recherches par mot, chacune hachant L lettres, soit O(n × 26 × L²) au total. Les deux méthodes sont plus efficaces que de comparer avec toute la liste.

La recherche en largeur bidirectionnelle peut-elle accélérer Word Ladder ?

Oui. Lance la recherche simultanément à partir de beginWord et de endWord, en développant toujours le côté le plus petit d’un niveau, et arrête-toi lorsqu’un nouveau mot a déjà été atteint par l’autre côté. L’échelle comporte alors un mot de plus que le nombre total de changements effectués des deux côtés. Si chaque mot a environ b voisins et que l’échelle nécessite d changements, une recherche peut parcourir environ b^d mots, tandis que deux recherches qui se rejoignent au milieu en parcourent environ 2 × b^(d/2).

Python

def ladderLength(beginWord, endWord, wordList):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

Attendu

Word Ladder

Fonction

Contraintes

Exemples

Indices

Solution

Essaie chaque échelle avec une recherche en profondeur

Parcours en largeur, comparaison de chaque paire

Recherche en largeur avec des compartiments à caractères génériques

Pièges et cas limites

Questions fréquentes4

Problèmes similaires