Word Ladder
Você recebe duas palavras, beginWord e endWord, e uma lista de palavras wordList. Uma escada 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, portanto endWord deve estar nela; beginWord não precisa estar.
Retorne o número de palavras na escada mais curta, contando as duas extremidades, ou 0 se não houver nenhuma.
Função
- beginWordstring
- a primeira palavra da escada
- endWordstring
- a palavra que a escada deve alcançar
- wordListstring-array
- as palavras de onde cada etapa posterior deve vir
- Retornainteger
- o número de palavras na menor sequência, ou 0 se não houver nenhuma
Restrições
1 ≤ beginWord.length ≤ 10endWorde cada palavra emwordListtêm o mesmo comprimento quebeginWord.1 ≤ wordList.length ≤ 5000- Todas as palavras contêm apenas letras minúsculas do inglês.
beginWord != endWord- As palavras em
wordListsão todas diferentes.beginWordpode ou não ser uma delas.
Exemplos
- Entrada
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- Saída
- 4
- Explicação
leadegolddiferem em três letras, então uma escada precisa de pelo menos 4 palavras, elead,load,goad,goldtem 4.lendelewdsão becos sem saída.
- Entrada
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- Saída
- 0
- Explicação
cat,cot,cogficam a uma letra dedog, masdognã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,cdeab,cb,cdcontêm 3 palavras cada.abtambém está na lista, mas o início é contado uma vez.
Para ir além
Você pode retornar uma sequência de palavras mais curta — com as palavras em ordem — em vez do comprimento dela?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Imagine cada palavra como um ponto e desenhe uma linha entre duas palavras que diferem em exatamente uma letra. O que é uma escada nessa representação e qual é a mais curta?
A escada mais curta é o caminho com menos linhas, e todas as linhas têm o mesmo peso. A busca em largura alcança todas as palavras a um passo de distância antes de qualquer palavra a dois passos de distância, então, na primeira vez que alcança
endWord, ela usou o menor número de passos. Marque uma palavra como visitada no momento em que você a alcançar pela primeira vez.Comparar uma palavra com a lista inteira para encontrar suas vizinhas é lento. Em vez disso, esconda uma letra por vez:
hot,hatehitse tornamh*t. Coloque cada palavra no grupo de cada um de seus padrões. As vizinhas de uma palavra são as outras palavras nos grupos dela. Execute a busca nível por nível a partir debeginWorde conte os níveis.
Solução
Trate as palavras como nós de um grafo, com uma aresta entre palavras que diferem por uma letra. Todas as arestas têm o mesmo custo, então a busca em largura encontra a escada mais curta. A parte difícil é encontrar as arestas rapidamente. 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
A partir da palavra atual, tente cada palavra não utilizada que difere por uma letra e avance, mantendo o comprimento ao chegar a endWord. Marque as palavras no caminho como usadas e libere-as ao voltar. Quando existir uma escada de best palavras, pare de estender caminhos de best-1 palavras.
Isso tenta todas as escadas sem repetir palavras, e uma escada mais curta nunca repete uma palavra: remover a parte entre duas ocorrências a encurtaria.
As 26 palavras aaa, baa até zaa diferem entre si por uma letra e podem ser ordenadas de cerca de 4 × 10^26 maneiras. Se endWord não puder ser alcançada, o corte nunca é acionado e a busca tenta todas elas.
Algoritmo
- Marque
beginWordcomo usado se ele estiver na lista e definabestcomo 0. search(word, length): emendWord, mantenhalengthse ele for menor quebeste retorne. Sebestestiver definido elength + 1 ≥ best, retorne.- Caso contrário, para cada palavra não usada que esteja a uma letra de distância, marque-a, chame
search(next, length + 1)e desmarque-a. - Retorne
bestapóssearch(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 bestBusca em largura, comparando cada par
Correta, mas não termina nos maiores testes
Intuição
Uma fila explora as palavras em ordem de distância: todas as palavras à distância d saem dela antes de qualquer palavra à distância d + 1. Portanto, quando uma palavra é alcançada pela primeira vez à distância d, todas as palavras mais próximas já foram exploradas, e uma sequência mais curta até ela teria chegado antes. Sua distância é definitiva no momento em que ela entra na fila, então marque-a como visitada nesse momento, e a distância da primeira vez que endWord aparece é a resposta.
Esta versão encontra os vizinhos de uma palavra comparando-a com todas as palavras da lista e parando na segunda diferença: O(n² × L), até 25 milhões de comparações de palavras para 5.000 palavras.
Algoritmo
- Se
endWordnão estiver emwordList, retorne 0. - Enfileire
beginWordcom comprimento 1, marcado como visitado se estiver na lista. - Pegue a próxima palavra e compare-a com cada palavra não visitada. Para cada palavra que estiver a uma letra de distância: se for
endWord, retorne comprimento + 1; caso contrário, marque-a e enfileire-a com comprimento + 1. - Se a fila ficar vazia, 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 0Busca em largura com buckets de curingas
Intuição
Duas palavras diferem por exatamente uma letra quando ocultar a mesma posição as torna iguais: hot e hit ambas se tornam h*t. Gere L padrões para cada palavra, um para cada posição ocultada, e adicione-a a um balde para cada padrão. As palavras vizinhas de uma palavra são as outras palavras em seus L baldes, encontradas com L consultas de hash em vez de percorrer a lista.
No primeiro exemplo, 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; *oad então fornece goad, e go*d fornece gold no nível 4.
Depois que um balde é percorrido, todas as palavras nele são alcançadas, então esvazie-o: o balde de 26 palavras *aa é percorrido uma vez, não 26 vezes. O custo é de O(n × L²) em tempo e espaço, cerca de 500.000 passos de letras para 5.000 palavras de 10 letras.
Algoritmo
- Se
endWordnão estiver emwordList, retorne 0. - Agrupe cada palavra, incluindo
beginWord, em cada um de seus padrões deL. - Enfileire
beginWord, marcado como visitado, no comprimento 1. - Para cada palavra de um nível: se for
endWord, retorne o comprimento. Caso contrário, mova cada palavra não visitada de cada um de seus grupos de padrões para o próximo nível, marque-a como visitada e esvazie o grupo. - Adicione 1 ao comprimento por nível. 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
- Contar as mudanças em vez das palavras.
leadparagoldsão 3 mudanças e 4 palavras; a resposta é 4. - Ignorar a verificação de que
endWordestá emwordList. O segundo exemplo chega acog, que está a uma letra dedog, mas a resposta é 0. - Marcar uma palavra como visitada quando ela sai da fila. Uma palavra no balde
*aapode então entrar até 25 vezes, e a fila cresce muito além den. - Fazer recursão ao longo da cadeia de palavras. Uma cadeia mais curta pode ter milhares de palavras, o suficiente para estourar a pilha de chamadas.
Perguntas frequentes3
Qual é a complexidade de tempo de Word Ladder?
Com buckets de curingas, o custo é O(n × L²) para n palavras de comprimento L: cada palavra tem L padrões de L letras. Comparar cada par de palavras custa O(n² × L), e tentar cada sequência com busca em profundidade é exponencial.
Como encontrar as palavras que estão a uma letra de distância?
Os buckets curinga são uma maneira. A outra é alterar cada posição para cada uma das 26 letras e procurar o resultado em um conjunto hash das palavras: 26 × L buscas de L letras por palavra, O(n × 26 × L²) no total. Ambos são mais eficientes do que percorrer a lista.
O BFS bidirecional pode tornar Word Ladder mais rápido?
Sim. Pesquise pelas duas extremidades ao mesmo tempo, sempre expandindo o lado menor em um nível, e pare quando os dois lados se encontrarem. Com cerca de b vizinhos por palavra e d alterações, uma busca pode percorrer cerca de b^d palavras; duas buscas que se encontram no meio percorrem cerca de 2 × b^(d/2).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def ladderLength(beginWord, endWord, wordList):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Saída Esperada
4