Word Search

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

Il caso peggiore è O(m·n·3^L) per una scacchiera m × n e una parola di lunghezza L . Ognuna delle m·n celle può avviare un percorso e, dopo il primo passo, ogni cella ha al massimo tre vicini non visitati da provare. Lo spazio aggiuntivo è O(L) per la ricorsione, più O(m·n) se copi la scacchiera per contrassegnarla.

MedioBacktracking Grafi

+10

Ti viene fornita una griglia di lettere board, rappresentata come 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 sulla griglia: inizia da una cella qualsiasi e, a ogni passo, spostati nella cella direttamente sopra, sotto, a sinistra o a destra di quella corrente, in modo che le celle visitate compongano word nell’ordine indicato. Non puoi usare la stessa cella più di una volta. Altrimenti restituisci false. Le lettere distinguono tra maiuscole e minuscole, quindi a e A sono diverse.

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 alla riga 0, colonna 0, poi vai a destra fino alla T, scendi fino alla O, vai a destra fino alla seconda O, vai a destra fino alla L e scendi fino alla S alla riga 2, colonna 3. Sono sei celle diverse, ciascuna adiacente a quella precedente.

Input: board = ["STAR", "POOL", "ENDS"]word = "POP"
Output: false
Spiegazione: La scacchiera ha una sola P, alla riga 1, colonna 0. Dopo P e O ti serve un'altra P, e l'unica è la cella da cui è iniziato il percorso, che non può essere usata due volte.

Input: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Output: false
Spiegazione: Ogni lettera di SAND è sulla griglia, ma il percorso si interrompe al primo passo: l’unica A si trova alla riga 0, colonna 2, e nessuna delle due S la tocca.

+23 test nascosti all’invio

Per approfondire

Invece di sì o no, puoi contare quante tracciature diverse di word contiene la griglia?

Suggerimenti

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

0 di 3 aperti

Soluzione

Nessuna formula risolve questo problema: devi cercare i percorsi nella griglia. Il backtracking lo fa considerando un percorso alla volta. Estendi il percorso di una lettera, contrassegni ogni cella mentre il percorso la occupa e rimuovi il contrassegno quando torni indietro, così una cella non viene mai riutilizzata all'interno di un percorso, ma resta libera per tutti gli altri percorsi. Nel caso peggiore, questa ricerca è esponenziale rispetto alla lunghezza della parola, il che va bene su una griglia di dimensioni massime 6 × 6. Due controlli semplici prima di iniziare, il conteggio delle lettere e la partenza dall'estremità della parola con le lettere più rare, spesso riducono il lavoro da decine di migliaia di passaggi a poche decine.

Backtracking con una griglia visitata

Intuizione

Immagina un albero decisionale. La prima scelta è la cella iniziale e deve contenere word[0]. Dopodiché, ogni nodo è un percorso che compone le prime i lettere e i suoi figli sono le celle adiacenti che contengono word[i] e che non fanno ancora parte del percorso. Un percorso che compone l’intera parola è un successo. Un percorso senza celle adiacenti di questo tipo è un vicolo cieco, quindi torni indietro per provare la scelta successiva.

Una griglia visited impone la regola dell’uso singolo. Segna una cella quando il percorso vi passa e deselezionala quando il percorso torna indietro. È questa deselezione che rende possibile il backtracking: una cella attraversata in un vicolo cieco deve essere di nuovo libera per il tentativo successivo. Sulla griglia AA / AB con la parola AAA, partendo dalla cella in alto a sinistra, scendendo ci si blocca in basso a sinistra (l’altra cella adiacente contiene B), e andando a destra ci si blocca in alto a destra. Se quelle celle restassero segnate, non si potrebbe mai trovare la risposta: in basso a sinistra, poi in alto a sinistra, poi in alto a destra.

Questa è la soluzione standard, ed è corretta e abbastanza veloce in questo caso. Il suo costo è il numero di percorsi che esplora. Dopo la prima mossa, ogni passo ha al massimo tre nuove direzioni, quindi una parola di L lettere può comportare circa m·n·3^L percorsi. Prendi una griglia 5 × 5 piena di A e la parola composta da 8 A seguite da una B. Ogni percorso di A è un prefisso valido e la ricerca li percorre tutti prima di scoprire che non esiste alcuna B: circa 65.000 controlli di celle per rispondere false. Ogni lettera aggiuntiva all’incirca raddoppia quel conteggio, ed è per questo che il prossimo approccio verifica alcune cose prima di avviare la ricerca.

Algoritmo

Crea una griglia visited delle dimensioni della scacchiera, con tutti i valori impostati su false.
Definisci dfs(r, c, i): restituisci false se (r, c) è fuori dalla griglia, è già stata visitata oppure la sua lettera non è word[i].
Se i è l’ultimo indice di word, restituisci true.
Segna (r, c) come visitata, prova i quattro vicini con i+1, poi rimuovi il segno e restituisci se uno dei vicini ha avuto successo.
Chiama dfs(r, c, 0) da ogni cella e restituisci true non appena una chiamata ha successo.

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 contrassegni in-place e potatura

Intuizione

Mantieni la stessa ricerca e apporta due modifiche. Per prima cosa, contrassegna le celle su una copia privata della griglia invece che in una griglia separata: sovrascrivi una cella con # mentre il percorso la occupa e riscrivi la lettera quando fai un passo indietro. # non è mai uguale a una lettera della parola, quindi anche il controllo della lettera rifiuta le celle che si trovano sul percorso, e il ripristino è lo stesso passaggio di annullamento di prima.

In secondo luogo, applica una potatura prima della ricerca. Conta le lettere. Se la parola richiede più copie di una lettera di quante ce ne siano sulla griglia, la risposta è false senza eseguire alcuna ricerca. Questo risolve il caso della griglia con sole A, che contiene 8 A e una B, senza alcuna ricerca, invece di eseguire circa 65.000 controlli. Parti dall'estremità più rara. Un percorso letto al contrario forma la parola invertita sulle stesse celle, quindi puoi cercare invece la parola invertita. Se l'ultima lettera è più rara sulla griglia della prima, inverti la parola. Ci sono meno celle da cui avviare la ricerca, e la lettera rara esclude le partenze errate al primo passaggio invece che all'ultimo.

La seconda regola è importante quando la lettera rara esiste, ma è irraggiungibile. Metti l'unica B in un angolo i cui due vicini sono C, e cerca 8 A seguite da una B. Il conteggio delle lettere dà esito positivo. Procedendo in avanti, la ricerca esplora comunque ogni percorso di A, circa 35.000 controlli di celle. Invertendo la parola, questa inizia con B, una sola cella può dare inizio alla ricerca, i suoi vicini non sono A e la ricerca termina dopo circa 30 controlli.

Il caso peggiore è ancora O(m·n·3^L): si può costruire una griglia e una parola in cui le lettere sono distribuite uniformemente e i percorsi senza uscita vengono trovati tardi. La potatura non cambia la risposta né il limite. Elimina i modi più comuni in cui la ricerca semplice spreca tempo, al costo di un passaggio per contare le lettere, e il divario aumenta rapidamente con la lunghezza della parola.

Algoritmo

Conta ogni lettera sulla griglia e nella parola. Se la parola richiede più occorrenze di una lettera di quante ce ne siano sulla griglia, restituisci false.
Se la griglia contiene più occorrenze di word[0] rispetto all'ultima lettera, inverti word.
Copia la griglia in una griglia di caratteri che puoi modificare.
Definisci dfs(r, c, i): fallisci se la cella non è word[i]; riesci se i è l'ultimo indice; altrimenti imposta la cella su #, prova ogni vicino entro i limiti con i+1, rimetti la lettera e restituisci se uno qualsiasi dei tentativi è riuscito.
Esegui dfs(r, c, 0) da ogni cella e restituisci true non appena uno dei tentativi riesce.

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

La maggior parte delle risposte errate dipende dalla marcatura e dai controlli dei limiti.

Non rimuovere la marcatura di una cella dopo un ramo non riuscito. La cella resta bloccata per tutti i percorsi successivi e, con AA / AB, la parola AAA risulta false.
Non marcare affatto le celle. Senza la marcatura, il percorso può tornare sulla cella da cui proviene e POP sulla griglia di esempio restituirebbe true.
Leggere la cella prima di controllare i limiti. In Python, board[-1] è l'ultima riga, non un errore, quindi un controllo dei limiti mancante fa sì che la griglia venga attraversata silenziosamente dall'altro lato.
Controllare se la parola è stata trovata solo dopo uno spostamento. Una parola di una sola lettera su una griglia di una sola cella, ["A"] con A, deve restituire true anche se la cella non ha vicini.
Marcare usando un carattere che può essere una lettera effettiva. Per esempio, cambiare maiuscole e minuscole di una cella dà problemi nelle griglie che usano sia a sia A.
Spostarsi in diagonale. Solo le quattro celle che condividono un lato contano come vicine.

Domande frequenti4

Qual è la complessità temporale di Word Search?

Il caso peggiore è O(m·n·3^L) per una scacchiera m × n e una parola di lunghezza L. Ognuna delle m·n celle può avviare un percorso e, dopo il primo passo, ogni cella ha al massimo tre vicini non visitati da provare. Lo spazio aggiuntivo è O(L) per la ricorsione, più O(m·n) se copi la scacchiera per contrassegnarla.

Perché deselezioni le celle in Word Search?

Un contrassegno indica che la cella si trova sul percorso corrente. Quando un ramo non riesce, la cella esce dal percorso e potrebbe servire a un percorso diverso. Se mantieni il contrassegno, le ricerche successive considereranno la cella già usata e potrebbero non trovare un tracciamento valido. Contrassegna all'ingresso, rimuovi il contrassegno all'uscita.

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

Prima della ricerca vengono eseguiti due controlli. Se la parola richiede più occorrenze di una lettera di quante la griglia ne contenga, puoi restituire false senza effettuare la ricerca. Inoltre, poiché un percorso letto al contrario forma la parola invertita, puoi iniziare dall’estremità con la lettera più rara, riducendo così il numero di celle di partenza e scartando prima i percorsi errati. Nessuno dei due controlli cambia il caso peggiore, e la ricerca semplice è già una soluzione completa. Su una griglia 5 × 5 di A con una parola che richiede una B mancante, trasformano circa 65.000 controlli delle celle in nessuno.

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

Word Search cerca una parola. Word Search II fornisce un elenco di parole e chiede quali compaiono sulla griglia. Eseguire questa ricerca una volta per parola ripete molto lavoro, quindi la soluzione abituale inserisce tutte le parole in un trie e attraversa la griglia una sola volta, abbandonando un percorso non appena nessuna parola inizia con le sue lettere.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

true