Word Search

Q: Qual é a complexidade de tempo da busca de palavras?

O(m·n·3^L) para um tabuleiro m × n e uma palavra de comprimento L : cada célula pode iniciar um caminho e, após o primeiro passo, cada célula tem no máximo três vizinhos não visitados. O espaço extra é O(L) para a recursão, mais O(m·n) para uma cópia do tabuleiro.

MédioBacktracking Grafos

+10

Você recebe uma grade de letras board, 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: comece em qualquer célula e, a cada passo, vá para a célula acima, abaixo, à esquerda ou à direita, de modo que as células visitadas formem word na ordem correta, sem usar uma célula duas vezes. Caso contrário, retorne false. As letras diferenciam maiúsculas de minúsculas.

Função

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

boardstring-array: a grade, uma sequência de letras por linha
wordstring: a palavra para rastrear
Retornaboolean: se é possível rastrear a palavra por células lado a lado, 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 do canto superior esquerdo, vá para a direita até T, desça até O, vá para a direita até O e L, e desça até o S abaixo do L. Nenhuma célula se repete.

Entrada: board = ["STAR", "POOL", "ENDS"]word = "POP"
Saída: false
Explicação: O tabuleiro tem um P. Depois de P e O, você precisa de outro P, e o único é a célula inicial, 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 único A, na linha 0, coluna 2, não toca em nenhum S.

Para ir além

Em vez de responder sim ou não, você consegue contar quantos traçados diferentes de word há no tabuleiro?

Dicas

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

0 de 3 abertas

Solução

Você precisa procurar os caminhos pela grade. O retrocesso constrói um caminho letra por letra, marcando cada célula enquanto ela faz parte do caminho e desmarcando-a ao voltar, para que nenhum caminho reutilize uma célula. A busca é exponencial em relação ao comprimento da palavra, o que é viável em um tabuleiro de 6 × 6.

Retrocesso com uma grade de visitados

Intuição

Um caminho que forma as primeiras i letras pode seguir para qualquer vizinho que contenha word[i] e não esteja no caminho. Sem um vizinho assim, ele chega a um beco sem saída, e você volta atrás.

É a desmarcação que torna isso correto: uma célula percorrida por um caminho sem saída precisa estar livre para a próxima tentativa. Em AA / AB com AAA, as duas tentativas a partir do canto superior esquerdo ficam presas. Se as células delas continuassem marcadas, a resposta — canto inferior esquerdo, depois canto superior esquerdo e, por fim, canto superior direito — não seria encontrada.

Depois do primeiro movimento, cada etapa tem no máximo três novas direções, então a busca pode explorar até m·n·3^L caminhos. Em um tabuleiro de 5 × 5 com A, 8 As e depois um B, ela faz cerca de 53.000 verificações de células antes de responder false.

Algoritmo

Crie uma grade visited, toda com valores false.
dfs(r, c, i): retorna false se (r, c) estiver fora da grade, já tiver sido visitada ou não corresponder a word[i]; retorna true se i for o último índice.
Caso contrário, marque (r, c), tente as quatro células vizinhas com i+1, desmarque-a e retorne se alguma tentativa foi bem-sucedida.
Retorne true se dfs(r, c, 0) for bem-sucedida a partir de qualquer célula.

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

Busca com retrocesso usando marcações in-place e poda

Intuição

Mantenha a busca, com duas mudanças. Marque as células em uma cópia do tabuleiro escrevendo # e restaure a letra ao voltar. # nunca corresponde a uma letra da palavra, então a verificação da letra também rejeita células no caminho.

Depois, faça a poda. Se a palavra precisar de mais ocorrências de alguma letra do que o tabuleiro contém, retorne false: isso resolve o tabuleiro só com A sem fazer nenhuma busca. Um caminho lido ao contrário forma a palavra invertida nas mesmas células, então buscar a palavra invertida dá a mesma resposta. Comece pela extremidade cuja letra é mais rara no tabuleiro: há menos células para iniciar, e inícios incorretos falham de imediato.

Com o único B em um canto entre dois Cs, a busca direta faz cerca de 35.000 verificações de células; com a palavra invertida, 27. O pior caso continua sendo O(m·n·3^L).

Algoritmo

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 que você possa alterar.
dfs(r, c, i): falhe se a célula não for word[i]; tenha sucesso no último índice; caso contrário, defina-a como #, tente cada vizinho dentro dos limites com i+1, restaure-a e retorne se algum teve sucesso.
Retorne true se dfs tiver sucesso a partir de qualquer célula.

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

Não desmarcar uma célula após um ramo que falhou: AAA em AA / AB resulta em false.
Não marcar de jeito nenhum: o caminho volta à sua última célula, e POP no tabuleiro de exemplo retorna true.
Ler a célula antes de verificar os limites: em Python, board[-1] é a última linha, então os caminhos dão a volta na grade.
Verificar se houve sucesso somente após um movimento: ["A"] com A deve retornar true.
Marcar trocando a capitalização de uma célula: em ["aA"], o a marcado é lido como um segundo A, então aAA resulta em true.

Perguntas frequentes3

Qual é a complexidade de tempo da busca de palavras?

O(m·n·3^L) para um tabuleiro m × n e uma palavra de comprimento L: cada célula pode iniciar um caminho e, após o primeiro passo, cada célula tem no máximo três vizinhos não visitados. O espaço extra é O(L) para a recursão, mais O(m·n) para uma cópia do tabuleiro.

Como a poda torna a Busca de Palavras mais rápida?

Conte primeiro as letras e retorne false se o tabuleiro tiver poucas letras de algum tipo. Em seguida, pesquise a partir do fim usando a letra mais rara, com a qual menos células podem começar. Nenhuma das verificações altera o pior caso.

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

Word Search II pergunta quais palavras de uma lista aparecem no tabuleiro. Pesquisar uma vez por palavra repete trabalho, então a solução usual coloca as palavras em uma trie e percorre o tabuleiro uma vez, abandonando um caminho quando nenhuma palavra começa com suas letras.

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

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

true