Word Search

Q: Qual é a complexidade de tempo da Busca de Palavras?

O pior caso é O(m·n·3^L) para um tabuleiro m × n e uma palavra de comprimento L . Cada uma das m·n células pode iniciar um caminho e, após o primeiro passo, cada célula tem no máximo três vizinhos não visitados para tentar. O espaço extra é O(L) para a recursão, mais O(m·n) se você copiar o tabuleiro para marcá-lo.

MédioBacktracking Grafos

+10

Você recebe uma grade de letras board, representada por uma lista de strings em que board[r][c] é a letra na linha r, coluna c, e uma string word.

Retorne true se for possível traçar word na grade: comece em qualquer célula e, a cada etapa, vá para a célula diretamente acima, abaixo, à esquerda ou à direita da célula atual, de modo que as células visitadas formem word na ordem. Um traçado não pode usar a mesma célula duas vezes. Caso contrário, retorne false. As letras diferenciam maiúsculas de minúsculas, então a e A são diferentes.

Função

exist(board: string-array, word: string) → boolean

boardstring-array: à grade, uma sequência de letras por linha
wordstring: a palavra para rastrear
Retornaboolean: se é possível rastrear a palavra passando por células adjacentes, usando cada uma no máximo uma vez

Restrições

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, e todas as linhas têm o mesmo comprimento.
1 ≤ word.length ≤ 20
board e word contêm apenas letras do alfabeto inglês, maiúsculas e minúsculas.

Exemplos

Entrada: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Saída: true
Explicação: Comece no S na linha 0, coluna 0, depois vá para a direita até T, para baixo até O, para a direita até o segundo O, para a direita até L e para baixo até o S na linha 2, coluna 3. São seis células diferentes, cada uma ao lado da anterior.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "POP"
Saída: false
Explicação: O tabuleiro tem um único P, na linha 1, coluna 0. Depois de P e O, você precisa de outro P, e o único é a célula em que o caminho começou, que não pode ser usada duas vezes.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Saída: false
Explicação: Todas as letras de SAND estão no tabuleiro, mas o caminho se interrompe no primeiro passo: o único A está na linha 0, coluna 2, e nenhuma das letras S está ao lado dele.

+23 testes ocultos ao enviar

Para ir além

Em vez de responder sim ou não, você consegue contar quantas sequências diferentes de word o tabuleiro contém?

Dicas

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

0 de 3 abertas

Solução

Nenhuma fórmula resolve isso: você precisa buscar os caminhos pela grade. O retrocesso faz isso com um caminho de cada vez. Você estende o caminho em uma letra, marca cada célula enquanto o caminho a ocupa e a desmarca ao voltar, assim, uma célula nunca é reutilizada dentro de um caminho, mas permanece livre para todos os outros caminhos. Essa busca é exponencial em relação ao comprimento da palavra no pior caso, o que é aceitável em um tabuleiro de no máximo 6 × 6. Duas verificações simples antes dela, uma contagem de letras e começar pela extremidade mais rara da palavra, muitas vezes reduzem o trabalho de dezenas de milhares de etapas para algumas dezenas.

Backtracking com uma grade visitada

Intuição

Imagine uma árvore de decisão. A primeira escolha é a célula inicial, e ela deve conter word[0]. Depois disso, cada nó é um caminho que forma as primeiras i letras, e seus filhos são os vizinhos que contêm word[i] e ainda não estão no caminho. Um caminho que forma a palavra inteira é um sucesso. Um caminho sem nenhum vizinho assim é um beco sem saída, e você volta atrás para tentar a próxima escolha.

Uma grade visited impõe a regra de usar cada célula uma única vez. Marque uma célula quando o caminho passar por ela e desmarque-a quando o caminho sair dela. É esse desmarcamento que torna isso um retrocesso: uma célula percorrida por um caminho sem saída precisa ficar livre novamente para a próxima tentativa. No tabuleiro AA / AB com a palavra AAA, começando pela célula superior esquerda, descer leva a um beco sem saída na célula inferior esquerda (seu outro vizinho é B), e ir para a direita leva a um beco sem saída na célula superior direita. Se essas células continuassem marcadas, a resposta — célula inferior esquerda, depois superior esquerda e, por fim, superior direita — nunca poderia ser encontrada.

Esta é a solução padrão, e ela está correta e é rápida o suficiente aqui. Seu custo é o número de caminhos que ela explora. Depois do primeiro movimento, cada etapa tem no máximo três novas direções, então uma palavra com L letras pode resultar em algo na ordem de m·n·3^L caminhos. Considere um tabuleiro de 5 × 5 cheio de A e a palavra com 8 As seguidos por um B. Todo caminho de As é um prefixo válido, e a busca percorre todos eles antes de descobrir que não existe nenhum B: cerca de 65.000 verificações de células para responder false. Cada letra extra aproximadamente dobra essa contagem, e é por isso que a próxima abordagem verifica algumas coisas antes de fazer a busca.

Algoritmo

Crie uma grade visited do tamanho do tabuleiro, com todos os valores falsos.
Defina dfs(r, c, i): retorne falso se (r, c) estiver fora da grade, tiver sido visitado ou sua letra não for word[i].
Se i for o último índice de word, retorne verdadeiro.
Marque (r, c) como visitado, tente os quatro vizinhos com i+1, depois desmarque-o e retorne se algum vizinho teve sucesso.
Chame dfs(r, c, 0) a partir de cada célula e retorne verdadeiro assim que uma chamada tiver sucesso.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Retrocesso com marcações no próprio lugar e poda

Intuição

Mantenha a mesma busca e faça duas alterações. Primeiro, marque as células em uma cópia privada do tabuleiro, em vez de usar uma grade separada: sobrescreva uma célula com # enquanto o caminho a ocupar e escreva a letra de volta ao retroceder. # nunca é igual a uma letra da palavra, então a verificação da letra também rejeita as células no caminho, e a restauração é a mesma etapa de desfazer de antes.

Segundo, faça a poda antes da busca. Conte as letras. Se a palavra precisar de mais ocorrências de alguma letra do que o tabuleiro contém, a resposta é false sem nenhuma busca. Isso responde ao tabuleiro só com A, com 8 As, e uma B sem nenhuma busca, em vez de cerca de 65.000 verificações. Comece pela extremidade mais rara. Um caminho lido de trás para frente forma a palavra invertida nas mesmas células, então você pode buscar a palavra invertida. Se a última letra for mais rara no tabuleiro do que a primeira, inverta a palavra. Menos células podem iniciar uma busca, e a letra rara descarta inícios incorretos já na primeira etapa, em vez de na última.

A segunda regra importa quando a letra rara existe, mas está fora de alcance. Coloque a única B em um canto cujos dois vizinhos sejam C, e busque 8 As e depois uma B. A contagem de letras é aprovada. Na busca para frente, ainda se percorrem todos os caminhos de A, cerca de 35.000 verificações de células. Na busca invertida, a palavra começa com B, apenas uma célula pode iniciar, seus vizinhos não são A, e a busca termina após cerca de 30 verificações.

O pior caso ainda é O(m·n·3^L): é possível construir um tabuleiro e uma palavra em que as letras estejam equilibradas e os caminhos sem saída apareçam tarde. A poda não altera a resposta nem o limite. Ela elimina as formas comuns pelas quais a busca simples desperdiça tempo, ao custo de uma passagem para contar as letras, e a diferença cresce rapidamente com o comprimento da palavra.

Algoritmo

Conte cada letra no tabuleiro e na palavra. Se a palavra precisar de mais ocorrências de alguma letra do que o tabuleiro tem, retorne false.
Se o tabuleiro tiver mais ocorrências de word[0] do que da última letra, inverta word.
Copie o tabuleiro para uma grade de caracteres que você possa alterar.
Defina dfs(r, c, i): falhe se a célula não for word[i]; tenha sucesso se i for o último índice; caso contrário, defina a célula como #, tente cada vizinho dentro dos limites com i+1, coloque a letra de volta e retorne se algum teve sucesso.
Execute dfs(r, c, 0) a partir de cada célula e retorne true assim que uma delas tiver sucesso.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Armadilhas e casos extremos

A maioria das respostas erradas se deve à marcação e às verificações dos limites.

Não desmarcar uma célula após uma ramificação malsucedida. A célula continua bloqueada para todos os caminhos posteriores, e em AA / AB a palavra AAA resulta em falso.
Não marcar de jeito nenhum. Sem isso, o caminho pode voltar à célula de onde veio, e POP no tabuleiro de exemplo retornaria verdadeiro.
Ler a célula antes de verificar os limites. Em Python, board[-1] é a última linha, não um erro, então a ausência de uma verificação de limites faz com que a busca volte silenciosamente ao início da grade.
Verificar se houve sucesso somente após um movimento. Uma palavra de uma letra em um tabuleiro de uma célula, ["A"] com A, deve retornar verdadeiro, mesmo que a célula não tenha vizinhos.
Marcar com um caractere que pode ser uma letra de verdade. Alterar maiúsculas e minúsculas de uma célula, por exemplo, falha em tabuleiros que usam tanto a quanto A.
Mover-se na diagonal. Apenas as quatro células que compartilham um lado contam como vizinhas.

Perguntas frequentes4

Qual é a complexidade de tempo da Busca de Palavras?

O pior caso é O(m·n·3^L) para um tabuleiro m × n e uma palavra de comprimento L. Cada uma das m·n células pode iniciar um caminho e, após o primeiro passo, cada célula tem no máximo três vizinhos não visitados para tentar. O espaço extra é O(L) para a recursão, mais O(m·n) se você copiar o tabuleiro para marcá-lo.

Por que você desmarca células no caça-palavras?

Uma marca significa que a célula está no caminho atual. Quando um ramo falha, a célula sai do caminho, e um caminho diferente pode precisar dela. Se você mantiver a marca, as buscas posteriores tratarão a célula como usada e poderão não encontrar um rastreamento válido. Marque ao entrar e desmarque ao sair.

Como a poda torna a busca por palavras mais rápida?

Duas verificações são feitas antes da busca. Se a palavra precisar de mais ocorrências de alguma letra do que o tabuleiro contém, você pode retornar false sem buscar. E, como um caminho lido ao contrário forma a palavra invertida, você pode começar por qualquer uma das extremidades, escolhendo a que tem a letra mais rara. Isso reduz o número de células iniciais e descarta caminhos incorretos mais cedo. Nenhuma das duas verificações altera o pior caso, e a busca simples, por si só, já é uma resposta completa. Em um tabuleiro 5 × 5 de A, com uma palavra que precisa de um B ausente, elas reduzem cerca de 65.000 verificações de células a nenhuma.

Qual é a diferença entre Word Search e Word Search II?

Word Search pergunta sobre uma palavra. Word Search II fornece uma lista de palavras e pergunta quais aparecem no tabuleiro. Executar essa busca uma vez por palavra repete muito trabalho, então a solução usual coloca todas as palavras em uma trie e percorre o tabuleiro uma vez, abandonando um caminho assim que nenhuma palavra começa com suas letras.

Python

def exist(board, word):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

Esperado

true