Word Search

Q: Qual è la complessità temporale di Word Search?

O(m·n·3^L) per una scacchiera m × n e una parola di lunghezza L : ogni cella può avviare un percorso e, dopo il primo passaggio, ogni cella ha al massimo tre vicini non visitati. Lo spazio aggiuntivo è O(L) per la ricorsione, più O(m·n) per una copia della scacchiera.

MedioBacktracking Grafi

+10

Ricevi una griglia di lettere board, un elenco di stringhe in cui board[r][c] è la lettera nella riga r, colonna c, e una stringa word.

Restituisci true se riesci a tracciare word: inizia da una cella qualsiasi e spostati ogni volta nella cella sopra, sotto, a sinistra o a destra, in modo che le celle visitate compongano word nell'ordine corretto, senza mai usare una cella due volte. Altrimenti, restituisci false. Le lettere distinguono tra maiuscole e minuscole.

Funzione

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

boardstring-array: la griglia, una stringa di lettere per riga
wordstring: la parola da ricalcare
Restituisceboolean: se la parola può essere tracciata attraverso celle adiacenti, ciascuna usata al massimo una volta

Vincoli

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6 e ogni riga ha la stessa lunghezza.
1 ≤ word.length ≤ 20
board e word contengono solo lettere inglesi, maiuscole e minuscole.

Esempi

Input: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Output: true
Spiegazione: Inizia dalla S in alto a sinistra, vai a destra fino alla T, scendi fino alla O, vai a destra fino alla O e alla L, quindi scendi fino alla S sotto la L. Nessuna cella si ripete.

Input: board = ["STAR", "POOL", "ENDS"]word = "POP"
Output: false
Spiegazione: La scheda ha una P. Dopo P e O ti serve un'altra P, e l'unica disponibile è la cella iniziale, che non può essere usata due volte.

Input: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Output: false
Spiegazione: Ogni lettera di SAND è sulla griglia, ma l’unica A, alla riga 0, colonna 2, non tocca nessuna S.

Per approfondire

Invece di sì o no, riesci a contare quante diverse tracce di word contiene la griglia?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Devi cercare i percorsi attraverso la griglia. Il backtracking costruisce un percorso una lettera alla volta, contrassegnando ogni cella mentre il percorso la include e rimuovendo il contrassegno al ritorno, così nessun percorso riutilizza una cella. La ricerca ha complessità esponenziale rispetto alla lunghezza della parola, cosa consentita da una griglia 6 × 6.

Backtracking con una griglia visitata

Intuizione

Un percorso che corrisponde alle prime i lettere prosegue verso un vicino che contiene word[i] e non si trova già sul percorso. Se non c'è un vicino del genere, è un vicolo cieco e si torna indietro.

È la deselezione che rende corretto questo procedimento: una cella attraversata da un vicolo cieco deve essere libera per il tentativo successivo. Con AA / AB e AAA, entrambi i tentativi dall'angolo in alto a sinistra si bloccano. Se le celle fossero rimaste contrassegnate, non si troverebbe la risposta: in basso a sinistra, poi in alto a sinistra, poi in alto a destra.

Dopo la prima mossa, ogni passo ha al massimo tre nuove direzioni, quindi la ricerca può esplorare fino a m·n·3^L percorsi. Su una griglia 5 × 5 di A con 8 A seguite da una B, esegue circa 53.000 controlli di celle prima di rispondere false.

Algoritmo

Crea una griglia visited, tutta impostata su false.
dfs(r, c, i): restituisce false se (r, c) è fuori dalla griglia, è già stata visitata o non corrisponde a word[i]; restituisce true se i è l'ultimo indice.
Altrimenti contrassegna (r, c), prova i quattro vicini con i+1, rimuovi il contrassegno e restituisci se almeno uno ha avuto successo.
Restituisci true se dfs(r, c, 0) ha successo partendo da una qualsiasi cella.

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

Backtracking con marcature in-place e potatura

Intuizione

Mantieni la ricerca, con due modifiche. Segna le celle su una copia della griglia scrivendo #, e ripristina la lettera al ritorno. # non corrisponde mai a una lettera della parola, quindi anche il controllo delle lettere rifiuta le celle sul percorso.

Poi applica il pruning. Se per la parola serve una quantità di una lettera maggiore di quella presente nella griglia, restituisci false: così rispondi alla griglia composta solo da A senza effettuare ricerche. Un percorso letto al contrario forma la parola invertita sulle stesse celle, quindi cercare la parola invertita dà la stessa risposta. Inizia dall’estremità con la lettera più rara nella griglia: ci sono meno celle da cui iniziare e i tentativi errati falliscono subito.

Con l’unica B in un angolo tra due C, la ricerca in avanti esegue circa 35.000 controlli di celle; al contrario, 27. Il caso peggiore resta O(m·n·3^L).

Algoritmo

Se la parola richiede più occorrenze di una lettera di quante ce ne siano sulla griglia, restituisci false.
Se sulla griglia ci sono più occorrenze di word[0] che dell'ultima lettera, inverti word.
Copia la griglia in una griglia modificabile.
dfs(r, c, i): fallisci se la cella non è word[i]; restituisci successo all'ultimo indice; altrimenti impostala su #, prova ogni cella adiacente entro i limiti con i+1, ripristinala e restituisci se una qualsiasi ha avuto successo.
Restituisci true se dfs ha successo a partire da una qualsiasi cella.

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

Trappole e casi limite

Non deselezionare una cella dopo un ramo fallito: AAA su AA / AB restituisce false.
Non contrassegnare affatto: il percorso torna sulla sua ultima cella e POP sulla griglia di esempio restituisce true.
Leggere la cella prima di controllare i limiti: in Python, board[-1] è l'ultima riga, quindi i percorsi si avvolgono attorno alla griglia.
Controllare se la ricerca è riuscita solo dopo uno spostamento: ["A"] con A deve restituire true.
Contrassegnare cambiando maiuscole e minuscole di una cella: su ["aA"], la a contrassegnata viene letta come una seconda A, quindi aAA restituisce true.

Domande frequenti3

Qual è la complessità temporale di Word Search?

O(m·n·3^L) per una scacchiera m × n e una parola di lunghezza L: ogni cella può avviare un percorso e, dopo il primo passaggio, ogni cella ha al massimo tre vicini non visitati. Lo spazio aggiuntivo è O(L) per la ricorsione, più O(m·n) per una copia della scacchiera.

In che modo la potatura rende più veloce Word Search?

Prima conta le lettere e restituisci false se la griglia ne contiene troppo poche di una. Poi cerca partendo dalla fine con la lettera più rara, da cui possono partire meno celle. Nessuno dei due controlli cambia il caso peggiore.

Qual è la differenza tra Word Search e Word Search II?

Word Search II chiede quali parole di un elenco compaiono sulla griglia. Cercare una parola alla volta ripete il lavoro, quindi la soluzione consueta inserisce le parole in un trie e percorre la griglia una sola volta, abbandonando un percorso quando nessuna parola inizia con le sue lettere.

def exist(board, word):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

true