Word Ladder (LeetCode 127): BFS com Padrões Curinga em Python

O problema Word Ladder (LeetCode 127) pede o comprimento da menor cadeia de uma palavra até outra, mudando uma letra por vez, onde cada passo precisa estar em uma lista dada. Caminho mais curto com passos iguais significa busca em largura. O truque que o torna rápido é agrupar palavras por padrões curinga como h*t, para não comparar todos os pares de palavras.

O problema

Dados beginWord, endWord e uma lista de palavras, retorne o número de palavras na menor sequência de transformação de beginWord até endWord, contando as duas pontas. Cada passo muda exatamente uma letra, e cada palavra para a qual você avança precisa estar na lista. Retorne 0 se não existir essa sequência.

Por que busca em largura

Trate cada palavra como um nó, com uma aresta entre duas palavras que diferem em uma letra. Cada aresta custa um passo, então a menor sequência é o caminho mais curto em um grafo sem pesos, e a busca em largura o encontra na primeira vez que chega à palavra final.

Construção de arestas por força bruta

Comparar todos os pares de palavras para ver se diferem em uma letra custa O(N ao quadrado vezes L) para N palavras de comprimento L. Com milhares de palavras isso fica lento. Melhor: gerar vizinhos a partir de padrões.

Abordagem: padrões curinga

Substitua cada letra, uma de cada vez, por *. hot vira *ot, h*t e ho*. Duas palavras são vizinhas exatamente quando compartilham um padrão. Construa um mapa de padrão para as palavras que se encaixam nele, depois rode a busca usando esse mapa.

from collections import deque, defaultdict

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    patterns = defaultdict(list)
    for w in words | {begin_word}:
        for i in range(len(w)):
            patterns[w[:i] + "*" + w[i + 1:]].append(w)
    queue = deque([(begin_word, 1)])
    seen = {begin_word}
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            key = word[:i] + "*" + word[i + 1:]
            for nxt in patterns[key]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
            patterns[key] = []
    return 0

Dois detalhes importam. A palavra inicial é adicionada ao mapa de padrões mesmo que não esteja na lista, já que você começa por ela. E depois que as palavras de um padrão são visitadas, patterns[key] = [] esvazia o grupo para que ele não seja varrido de novo a partir de cada outra palavra que compartilha o padrão. Isso mantém o trabalho total linear no número de padrões.

Complexidade

Construir os padrões leva O(N vezes L), e cada string de padrão custa O(L) para ser montada, então dá cerca de O(N vezes L ao quadrado) no total. A busca toca cada palavra uma vez e cada grupo de padrão uma vez, pelo mesmo limite. O espaço é O(N vezes L ao quadrado) para o mapa de padrões, já que cada palavra é armazenada sob L chaves de comprimento L.

Para ir mais rápido: busca bidirecional

Rode uma busca a partir da palavra inicial e outra a partir da palavra final, e sempre expanda a fronteira menor. Elas se encontram no meio, então cada lado busca apenas metade da profundidade. Vale mencionar se o entrevistador perguntar como acelerar, e dá mais código do que a maioria das entrevistas espera que você escreva.

Erros comuns

• Retornar o número de mudanças em vez do número de palavras. A sequência inclui beginWord, então o exemplo dá 5, não 4.
• Não verificar se endWord está na lista antes de buscar.
• Construir vizinhos com comparação par a par e estourar o tempo.
• Deixar a busca revisitar palavras, o que gera loop ou a deixa lenta.
• Usar DFS, que encontra um caminho mas não o mais curto.

Casos extremos para testar

Como explicar na entrevista

1. Reenquadre como um grafo e diga por que a busca em largura encontra o caminho mais curto.
2. Diga que a comparação par a par é lenta demais e introduza os padrões curinga.
3. Escreva o mapa de padrões, a fila e o conjunto de visitados.
4. Diga que você conta palavras, não edições, e mostre o primeiro exemplo.
5. Dê a complexidade e mencione a busca bidirecional.

Testei o código acima contra uma busca em largura simples par a par em 20.000 listas pequenas de palavras aleatórias, além dos dois exemplos da tabela, antes de publicar. Uma checagem aleatória rápida assim é um bom hábito na hora de praticar.

Prática relacionada

Veja nossa cola de Big O para os termos de complexidade, a lista LeetCode Blind 75 para o que praticar em seguida, e o guia do assistente de entrevista de programação para saber como praticar.

Fale em voz alta sobre sua abordagem enquanto programa. Uma transcrição mostra se você declarou a observação-chave antes de escrever. Siga as regras da empresa sobre ferramentas de IA em qualquer avaliação ao vivo.