Word Ladder

Q: Quelle est la complexité temporelle de Word Ladder ?

Avec des compartiments génériques, la complexité est de O(n × L²) pour n mots de longueur L : chaque mot possède L motifs de L lettres. Comparer chaque paire de mots coûte O(n² × L) , et essayer chaque échelle avec une recherche en profondeur est exponentiel.

DifficileGraphes File

+10

On te donne deux mots, beginWord et endWord, ainsi qu’une liste de mots wordList. Une chaîne commence par beginWord, se termine par endWord et change exactement une lettre d’un mot au suivant. Chaque mot après beginWord doit provenir de wordList, donc endWord doit s’y trouver ; ce n’est pas nécessaire pour beginWord.

Renvoie le nombre de mots de la chaîne la plus courte, en comptant les deux extrémités, ou 0 s’il n’y en a aucune.

Fonction

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

beginWordstring: le premier mot de l’échelle
endWordstring: le mot the ladder doit atteindre
wordListstring-array: les mots dont chaque étape ultérieure doit provenir
Renvoieinteger: le nombre de mots dans la séquence 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 minuscules de l’alphabet anglais.
beginWord != endWord
Les mots de wordList sont tous différents. beginWord peut ou non en faire partie.

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 une échelle nécessite au moins 4 mots, et lead, load, goad, gold en contient 4. lend et lewd sont des impasses.

Entrée: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Sortie: 0
Explication: cat, cot, cog ne sont qu'à une lettre de dog, 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 comportent tous deux 3 mots. ab figure également dans la liste, mais le début n'est compté qu'une seule fois.

Pour aller plus loin

Peux-tu renvoyer une des séquences les plus courtes elle-même, avec les mots dans l’ordre, plutôt que 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 des nœuds d’un graphe, avec une arête entre les mots qui diffèrent d’une lettre. Toutes les arêtes ont le même coût, donc le parcours en largeur trouve la chaîne la plus courte. Le plus difficile est de trouver rapidement les arêtes. 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

À partir du mot actuel, essaie chaque mot inutilisé qui diffère d’une lettre et explore plus profondément, en conservant la longueur lorsque tu atteins endWord. Marque comme utilisés les mots du chemin, puis libère-les en revenant en arrière. Une fois qu’une échelle de best mots existe, cesse de prolonger les chemins de best-1 mots.

Cela essaie toutes les échelles sans mot répété, et une échelle la plus courte ne répète jamais de mot : supprimer la partie entre deux occurrences la raccourcirait.

Les 26 mots aaa, baa jusqu’à zaa ne diffèrent tous que d’une lettre et peuvent être ordonnés d’environ 4 × 10^26 façons. Si endWord est inaccessible, l’élagage ne se déclenche jamais et la recherche les essaie tous.

Algorithme

Marquez beginWord comme utilisé s’il figure dans la liste, et définissez best à 0.
search(word, length) : à endWord, conservez length s’il est inférieur à best, puis retournez. Si best est défini et que length + 1 ≥ best, retournez.
Sinon, pour chaque mot inutilisé situé à une lettre de distance, marquez-le, appelez search(next, length + 1), puis démarquez-le.
Retournez best après search(beginWord, 1).

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

Recherche en largeur, en comparant chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une file explore les mots par ordre de distance : tous les mots à la distance d en sortent avant tout mot à la distance d + 1. Ainsi, lorsqu’un mot est atteint pour la première fois à la distance d, tous les mots plus proches ont déjà été explorés, et un chemin plus court jusqu’à ce mot l’aurait atteint plus tôt. Sa distance est définitive dès qu’il rejoint la file ; marque-le donc comme visité à ce moment-là, et la distance de endWord est la réponse dès qu’il apparaît pour la première fois.

Cette version trouve les voisins d’un mot en le comparant à chaque mot de la liste, en s’arrêtant à la deuxième différence : O(n² × L), soit jusqu’à 25 millions de comparaisons de mots pour 5 000 mots.

Algorithme

Si endWord ne se trouve pas dans wordList, renvoie 0.
Ajoute beginWord à la file avec une longueur de 1, en le marquant comme visité s’il se trouve dans la liste.
Prends le mot suivant et compare-le à chaque mot non visité. Pour chaque mot qui diffère d’une seule lettre : s’il s’agit de endWord, renvoie longueur + 1 ; sinon, marque-le comme visité et ajoute-le à la file avec une longueur de + 1.
Si la file devient vide, 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 à jokers

Intuition

Deux mots sont séparés exactement d’une lettre lorsque masquer la même position les rend identiques : hot et hit deviennent tous deux h*t. Donne à chaque mot L motifs, un par position masquée, puis ajoute-le à un compartiment pour chacun. Les voisins d’un mot sont les autres mots de ses compartiments L, trouvés par L recherches dans la table de hachage plutôt qu’en parcourant la liste.

Dans le premier exemple, l*ad contient load et le*d contient lend et lewd, donc le niveau 2 comprend ces trois mots ; *oad donne ensuite goad, et go*d donne gold au niveau 4.

Une fois qu’un compartiment a été parcouru, tous ses mots ont été atteints, alors vide-le : le compartiment de 26 mots *aa est parcouru une seule fois, et non 26 fois. Le coût est de O(n × L²) en temps et en espace, soit environ 500 000 opérations sur des lettres pour 5 000 mots de 10 lettres.

Algorithme

Si endWord ne se trouve pas dans wordList, renvoie 0.
Place chaque mot, y compris beginWord, dans chacun de ses compartiments de motifs L.
Ajoute beginWord à la file, marqué comme visité, avec une longueur de 1.
Pour chaque mot d’un niveau : si c’est endWord, renvoie la longueur. Sinon, déplace chaque mot non visité de chacun de ses compartiments de motifs au niveau suivant, marque-le comme visité et vide le compartiment.
Ajoute 1 à la longueur à chaque niveau. 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

Compter les changements plutôt que les mots. lead à gold représente 3 changements et 4 mots ; la réponse est 4.
Omettre de vérifier que endWord figure dans wordList. Le deuxième exemple atteint cog, à une lettre de dog, mais la réponse est 0.
Marquer un mot comme visité lorsqu’il quitte la file. Un mot du groupe *aa peut alors être ajouté jusqu’à 25 fois, et la file dépasse largement n.
Parcourir l’échelle par récursion. Une échelle la plus courte peut compter des milliers de mots, ce qui suffit à faire déborder la pile d’appels.

Questions fréquentes3

Quelle est la complexité temporelle de Word Ladder ?

Avec des compartiments génériques, la complexité est de O(n × L²) pour n mots de longueur L : chaque mot possède L motifs de L lettres. Comparer chaque paire de mots coûte O(n² × L), et essayer chaque échelle avec une recherche en profondeur est exponentiel.

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

Les compartiments avec caractères génériques constituent une méthode. L’autre consiste à remplacer chaque position par chacune des 26 lettres et à rechercher le résultat dans un ensemble de hachage contenant les mots : 26 × L recherches de L lettres par mot, soit O(n × 26 × L²) au total. Les deux méthodes sont plus rapides qu’un parcours de la liste.

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

Oui. Lance une recherche depuis les deux extrémités à la fois, en élargissant toujours le côté le plus petit d’un niveau, et arrête-toi lorsque les deux côtés se rejoignent. Avec environ b voisins par mot et d changements, une recherche peut parcourir environ b^d mots ; deux recherches qui se rejoignent au milieu en parcourent environ 2 × b^(d/2).

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

Word Ladder

Fonction

Contraintes

Exemples

Indices

Solution

Essaie chaque échelle avec une recherche en profondeur

Recherche en largeur, en comparant chaque paire

Recherche en largeur avec des compartiments à jokers

Pièges et cas limites

Questions fréquentes3

Problèmes similaires