Word Ladder

Q: Uma busca em largura bidirecional pode tornar o Word Ladder mais rápido?

Sim. Pesquise a partir de beginWord e de endWord ao mesmo tempo, sempre expandindo o lado menor em um nível, e pare quando uma nova palavra já tiver sido alcançada pelo outro lado. A escada terá então uma palavra a mais do que as alterações feitas nos dois lados em conjunto. Se cada palavra tiver cerca de b vizinhas e a escada exigir d alterações, uma busca poderá percorrer cerca de b^d palavras, enquanto duas buscas que se encontram no meio percorrem cerca de 2 × b^(d/2) .

DifícilGrafos Fila

+10

Você recebe duas palavras, beginWord e endWord, e uma lista de palavras wordList. Uma escada é uma sequência de palavras que começa com beginWord, termina com endWord e altera exatamente uma letra de cada palavra para a próxima. Todas as palavras após beginWord devem vir de wordList.

Retorne o número de palavras na escada mais curta, contando as duas extremidades, ou 0 se não houver escada. Por exemplo, cold, cord, card formam uma escada de 3 palavras. beginWord não precisa estar em wordList, mas endWord precisa.

Função

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

beginWordstring: a primeira palavra da escada
endWordstring: a palavra the ladder deve alcançar
wordListstring-array: as palavras de que cada etapa posterior deve partir
Retornainteger: o número de palavras na menor cadeia, ou 0 se não houver nenhuma

Restrições

1 ≤ beginWord.length ≤ 10
endWord e cada palavra em wordList tem o mesmo comprimento que beginWord.
1 ≤ wordList.length ≤ 5000
Todas as palavras contêm apenas letras minúsculas do inglês.
beginWord != endWord
As palavras em wordList são todas diferentes. beginWord pode ou não ser uma delas.

Exemplos

Entrada: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Saída: 4
Explicação: lead e gold diferem em três letras, então nenhuma escada tem menos de 4 palavras, e lead, load, goad, gold tem exatamente 4 palavras. lend e lewd também diferem de lead por uma letra, mas nenhuma das duas leva a algum lugar novo, e só é possível chegar a bold a partir de gold.

Entrada: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Saída: 0
Explicação: cat, cot, cog chegam a uma letra de distância de dog, mas dog não está na lista, então nenhuma escada pode terminar ali.

Entrada: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Saída: 3
Explicação: ab, ad, cd e ab, cb, cd têm 3 palavras. ab também está na lista, mas o início é contado uma vez de qualquer forma.

+14 testes ocultos ao enviar

Para ir além

Você consegue retornar uma das menores escadas em si, com as palavras em ordem, e não apenas o seu comprimento?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Considere as palavras como os nós de um grafo, com uma aresta entre duas palavras que diferem em uma letra. Uma escada é, então, um caminho de beginWord até endWord, e todas as arestas têm o mesmo custo; portanto, a escada mais curta é o caminho com o menor número de arestas. A busca em largura encontra exatamente isso. O que torna o problema difícil é encontrar as arestas rapidamente: comparar cada par de 5.000 palavras resulta em 25 milhões de comparações, então a melhor solução procura os vizinhos por meio de padrões curinga. Abaixo, n é o número de palavras e L, o comprimento delas.

Tente cada escada com busca em profundidade

Correta, mas não termina nos maiores testes

Intuição

Comece em beginWord. A partir da palavra atual, tente cada palavra ainda não usada que esteja a uma letra de distância e avance a partir dela. Quando chegar a endWord, registre o comprimento da escada se ele for o menor até então. Marque como usadas as palavras do caminho atual para que uma escada nunca volte sobre si mesma, e libere cada palavra ao retornar dela para que outras escadas possam usá-la. Assim que você tiver uma escada com best palavras, pare de estender qualquer caminho que já tenha best-1 palavras: ele não pode terminar com menos palavras.

Isso está correto porque tenta todas as escadas que nunca repetem uma palavra, e uma escada mais curta nunca repete nenhuma: se uma palavra aparecesse duas vezes, remover o trecho entre as duas ocorrências produziria uma escada mais curta.

É lento porque o número de escadas cresce vertiginosamente. Considere 26 palavras que diferem apenas na primeira letra, aaa, baa até zaa: cada par está a uma letra de distância, então a busca pode percorrê-las em qualquer ordem antes de prosseguir, e 26 palavras podem ser ordenadas de cerca de 4 × 10^26 maneiras. O corte só ajuda depois que alguma escada é encontrada. Quando endWord não pode ser alcançada, nada é cortado, e uma lista de 34 palavras já é mais do que a busca consegue terminar. A recursão também pode atingir uma profundidade igual ao comprimento da escada, que pode ter milhares de palavras.

Algoritmo

Marque beginWord como usado se ele estiver na lista e defina best como 0.
Escreva search(word, length). Se word for endWord, mantenha length quando ele superar best e retorne.
Se best não for 0 e length + 1 ≥ best, retorne: este caminho não pode vencer.
Para cada palavra não usada que esteja a uma letra de distância de word, marque-a como usada, chame search(next, length + 1) e depois desmarque-a.
Chame search(beginWord, 1) e retorne best, que permanece 0 se não existir nenhuma sequência.

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

Busca em largura, comparando cada par

Correta, mas não termina nos maiores testes

Intuição

A busca em largura explora as palavras em ordem de distância. Primeiro, beginWord, uma escada de 1 palavra. Depois, cada palavra a uma letra de distância dela, escadas de 2. Em seguida, cada nova palavra a uma letra de distância dessas, escadas de 3, e assim por diante. Uma fila mantém essa ordem: as palavras saem dela na ordem em que entraram, então todas as palavras à distância d saem antes de qualquer palavra à distância d + 1.

Essa ordem é o motivo pelo qual a primeira escada encontrada pela BFS é a mais curta. Quando uma palavra é alcançada pela primeira vez à distância d, todas as palavras mais próximas do que d já foram exploradas; portanto, se existisse uma escada mais curta até ela, a busca teria alcançado a palavra antes. O mesmo argumento torna seguro marcar uma palavra como visitada no momento em que ela entra na fila: sua distância é definitiva, e alcançá-la novamente mais tarde só pode resultar em um caminho mais longo. Assim, cada palavra entra na fila uma única vez e, assim que endWord aparece como vizinha, sua distância é a resposta.

Esta versão encontra as vizinhas de uma palavra comparando-a com cada palavra da lista, letra por letra, e parando na segunda diferença. Cada uma das até n palavras que saem da fila custa n comparações de até L letras, totalizando O(n² × L). Com 5.000 palavras e uma busca que visita a maioria delas, isso pode chegar a 25 milhões de comparações entre palavras. Uma linguagem compilada dá conta disso rapidamente, mas o Python precisa de vários segundos no maior teste.

Algoritmo

Se endWord não estiver em wordList, retorne 0.
Coloque beginWord em uma fila com comprimento 1. Marque-o como visitado se estiver na lista.
Retire da fila a próxima palavra e seu comprimento.
Compare-a com cada palavra não visitada da lista. Para cada uma que estiver a exatamente uma letra de distância: se for endWord, retorne comprimento + 1; caso contrário, marque-a como visitada e adicione-a com comprimento + 1.
Se a fila ficar vazia, endWord é inalcançável: retorne 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

Busca em largura com grupos de curingas

Intuição

Mantenha a busca em largura e torne barata a busca por vizinhos. Duas palavras diferem por exatamente uma letra quando, ao ocultar a mesma posição em ambas, elas ficam iguais: hot e hit se tornam h*t. Portanto, dê a cada palavra L padrões, um para cada posição ocultada, e adicione a palavra a um compartimento para cada padrão. Os vizinhos de uma palavra são as outras palavras em seus L compartimentos, encontrados com L consultas de hash, em vez de percorrer a lista inteira.

Veja a busca no primeiro exemplo. lead tem os padrões *ead, l*ad, le*d e lea*. O compartimento l*ad contém load e le*d contém lend e lewd, então o nível 2 contém essas três palavras. A partir de load, o compartimento *oad fornece goad no nível 3 e, a partir de goad, go*d fornece gold no nível 4.

Mais uma economia: quando o compartimento de uma palavra tiver sido percorrido, todas as palavras nele já terão sido alcançadas, então esvazie-o. Palavras posteriores que compartilham o padrão não encontrariam nada de novo nele. No teste em que aaa, baa até zaa compartilham *aa, esse compartimento de 26 palavras é percorrido uma vez, em vez de 26 vezes. Assim, a busca lê cada uma das n × L entradas dos compartimentos no máximo uma vez.

Construir os padrões requer n × L strings de L letras, tempo e espaço O(n × L²), e a busca tem o mesmo custo: cada palavra removida da fila constrói seus L padrões novamente. Para 5.000 palavras de 10 letras, isso representa cerca de 500.000 etapas de letras, contra até 250 milhões na comparação par a par.

Algoritmo

Se endWord não estiver em wordList, retorne 0.
Para cada palavra da lista e para beginWord, adicione a palavra ao bucket de cada um de seus padrões L.
Inicie a fila com beginWord, marque-o como visitado e defina o comprimento como 1.
Processe a fila um nível por vez. Se uma palavra for endWord, retorne o comprimento. Caso contrário, para cada um de seus padrões, adicione ao próximo nível todas as palavras não visitadas daquele bucket, marque-as como visitadas e esvazie o bucket.
Após cada nível, adicione 1 ao comprimento. Se a fila ficar vazia, retorne 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

Armadilhas e casos extremos

A maioria das respostas erradas ocorre por contar a coisa errada ou por causa da regra sobre endWord.

Retornar o número de alterações em vez do número de palavras. De lead a gold são 3 alterações e 4 palavras, e a resposta é 4.
Não verificar se endWord está em wordList. No segundo exemplo, a busca obtém uma letra de dog, mas a resposta é 0.
Usar busca em profundidade e retornar a primeira sequência encontrada. A busca em profundidade segue um ramo até o fim, então sua primeira sequência costuma ser longa.
Marcar uma palavra como visitada quando ela sai da fila, em vez de quando entra. Assim, uma palavra em um grupo completo de 26 pode entrar na fila até 25 vezes, e a fila cresce muito além de n.
Deixar beginWord sem marcação quando também está em wordList. A busca então o alcança novamente dois níveis depois e repete o trabalho. Marque-o como visitado desde o início.
Testar palavras que diferem em no máximo uma letra. Toda palavra difere de si mesma em zero letras, então a condição é exatamente uma.
Fazer chamadas recursivas ao longo da sequência. Um teste oculto tem uma sequência mais curta de 1,500 palavras, profunda o bastante para estourar a pilha de chamadas em algumas linguagens. A busca em largura precisa apenas de uma fila.

Perguntas frequentes4

Por que a busca em largura encontra a menor escada de palavras?

O BFS explora as palavras em etapas: primeiro a palavra inicial, depois todas as palavras que estão a uma alteração de distância e, em seguida, todas as palavras que estão a duas alterações de distância. Uma palavra é alcançada pela primeira vez na etapa mais inicial que pode alcançá-la, então sua distância é o menor número possível de alterações. Isso só funciona porque todas as alterações têm o mesmo custo. Se cada etapa tivesse custos diferentes, você precisaria usar o algoritmo de Dijkstra.

Qual é a complexidade de tempo de Word Ladder?

Com buckets curinga, construir os padrões e executar a busca leva tempo O(n × L²) para n palavras de comprimento L, já que cada palavra tem L padrões de L letras. Comparar cada par de palavras custa O(n² × L), e tentar cada escada com busca em profundidade é exponencial.

Como encontrar as palavras que diferem por uma letra?

Uma maneira é usar os buckets com curingas acima: palavras que compartilham um padrão, como h*t, são vizinhas. A outra é substituir cada posição da palavra por cada uma das 26 letras e procurar o resultado em um conjunto hash das palavras. Isso custa 26 × L consultas por palavra, cada uma calculando o hash de L letras, totalizando O(n × 26 × L²). Ambas as opções são melhores do que comparar com a lista inteira.

Uma busca em largura bidirecional pode tornar o Word Ladder mais rápido?

Sim. Pesquise a partir de beginWord e de endWord ao mesmo tempo, sempre expandindo o lado menor em um nível, e pare quando uma nova palavra já tiver sido alcançada pelo outro lado. A escada terá então uma palavra a mais do que as alterações feitas nos dois lados em conjunto. Se cada palavra tiver cerca de b vizinhas e a escada exigir d alterações, uma busca poderá percorrer cerca de b^d palavras, enquanto duas buscas que se encontram no meio percorrem cerca de 2 × b^(d/2).

Python

def ladderLength(beginWord, endWord, wordList):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Word Ladder

Função

Restrições

Exemplos

Dicas

Solução

Tente cada escada com busca em profundidade

Busca em largura, comparando cada par

Busca em largura com grupos de curingas

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos