Word Search

Q: Jaka jest złożoność czasowa wyszukiwania słów?

O(m·n·3^L) dla planszy m × n i słowa o długości L : każda komórka może być początkiem ścieżki, a po pierwszym kroku każda komórka ma co najwyżej trzech nieodwiedzonych sąsiadów. Dodatkowa pamięć to O(L) na rekurencję oraz O(m·n) na kopię planszy.

ŚrednieNawroty Grafy

+10

Otrzymujesz siatkę liter board, listę ciągów znaków, w której board[r][c] to litera w wierszu r, kolumnie c, oraz ciąg znaków word.

Zwróć true, jeśli możesz odtworzyć word: zacznij na dowolnym polu i za każdym razem przejdź na pole powyżej, poniżej, po lewej lub po prawej, tak aby odwiedzane pola tworzyły kolejno word. Nie możesz użyć żadnego pola więcej niż raz. W przeciwnym razie zwróć false. Wielkość liter ma znaczenie.

Funkcja

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

boardstring-array: siatka, jeden ciąg liter w każdym wierszu
wordstring: słowo do przepisania
Zwracaboolean: czy słowo można prześledzić przez sąsiadujące ze sobą komórki, używając każdej z nich najwyżej raz

Ograniczenia

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, a każdy wiersz ma tę samą długość.
1 ≤ word.length ≤ 20
board i word zawierają tylko angielskie litery, małe i wielkie.

Przykłady

Wejście: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Wyjście: true
Wyjaśnienie: Zacznij w lewym górnym rogu na S, przejdź w prawo do T, w dół do O, w prawo do O i L, a następnie w dół do S pod L. Żadne pole się nie powtarza.

Wejście: board = ["STAR", "POOL", "ENDS"]word = "POP"
Wyjście: false
Wyjaśnienie: Plansza ma jedno P. Po P i O potrzebujesz kolejnego P, a jedyne takie pole to pole startowe, którego nie można użyć dwa razy.

Wejście: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Wyjście: false
Wyjaśnienie: Każda litera z SAND znajduje się na planszy, ale jedyne A, w wierszu 0, kolumnie 2, nie dotyka żadnego S.

Pytanie dodatkowe

Zamiast odpowiadać tak lub nie, możesz policzyć, ile różnych ścieżek dla word znajduje się na planszy?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Musisz przeszukać ścieżki w siatce. Przeszukiwanie z nawrotami rozbudowuje jedną ścieżkę, dodając po jednej literze naraz, oznacza każdą komórkę, gdy należy ona do ścieżki, i odznacza ją podczas cofania, dzięki czemu żadna ścieżka nie używa ponownie tej samej komórki. Wyszukiwanie ma złożoność wykładniczą względem długości słowa, na co pozwala plansza 6 × 6.

Cofanie się z użyciem siatki odwiedzonych pól

Intuicja

Ścieżka, która odpowiada pierwszym i literom, prowadzi dalej do dowolnego sąsiada zawierającego word[i], który nie należy do ścieżki. Jeśli nie ma takiego sąsiada, trafiasz w ślepy zaułek i cofasz się.

To cofnięcie oznaczenia sprawia, że algorytm działa poprawnie: pole, przez które przeszedł ślepy zaułek, musi być wolne przy kolejnej próbie. Na planszy AA / AB ze słowem AAA obie próby rozpoczęte w lewym górnym rogu kończą się niepowodzeniem. Gdyby pola pozostały oznaczone, odpowiedź — lewy dolny róg, następnie lewy górny róg, a potem prawy górny róg — zostałaby pominięta.

Po pierwszym ruchu każdy krok ma najwyżej trzy nowe kierunki, więc wyszukiwanie może sprawdzić do m·n·3^L ścieżek. Na planszy 5 × 5 wypełnionej literą A, z 8 literami A, a następnie literą B, algorytm wykonuje około 53 000 sprawdzeń pól, zanim zwróci false.

Algorytm

Utwórz tablicę visited, wypełnioną wartościami false.
dfs(r, c, i): zwróć false, jeśli (r, c) znajduje się poza tablicą, zostało odwiedzone lub nie jest równe word[i]; zwróć true, jeśli i jest ostatnim indeksem.
W przeciwnym razie oznacz (r, c), sprawdź czterech sąsiadów z i+1, usuń oznaczenie i zwróć informację, czy którekolwiek wywołanie zakończyło się powodzeniem.
Zwróć true, jeśli dfs(r, c, 0) zakończy się powodzeniem dla dowolnej komórki.

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

Wycofywanie się z użyciem znaczników w miejscu i przycinania

Intuicja

Kontynuuj wyszukiwanie, wprowadzając dwie zmiany. Oznaczaj pola na kopii planszy, wpisując #, a podczas cofania przywracaj literę. # nigdy nie pasuje do litery ze słowa, więc sprawdzanie liter odrzuca również pola na ścieżce.

Następnie przycinaj wyszukiwanie. Jeśli słowo wymaga większej liczby wystąpień jakiejś litery, niż zawiera plansza, zwróć false: pozwala to obsłużyć planszę z samymi A bez wyszukiwania. Ścieżka odczytana od tyłu tworzy odwrócone słowo na tych samych polach, więc wyszukiwanie odwróconego słowa daje tę samą odpowiedź. Zacznij od końca, którego litera występuje na planszy rzadziej: można zacząć na mniejszej liczbie pól, a błędne początki są odrzucane od razu.

Gdy jedyne B znajduje się w rogu między dwoma C, wyszukiwanie w przód wykonuje około 35,000 sprawdzeń pól; po odwróceniu — 27. Złożoność w najgorszym przypadku pozostaje O(m·n·3^L).

Algorytm

Jeśli słowo wymaga większej liczby wystąpień którejkolwiek litery, niż jest jej na planszy, zwróć false.
Jeśli na planszy jest więcej wystąpień word[0] niż ostatniej litery, odwróć word.
Skopiuj planszę do siatki, którą możesz modyfikować.
dfs(r, c, i): zakończ niepowodzeniem, jeśli komórka nie zawiera word[i]; zakończ powodzeniem przy ostatnim indeksie; w przeciwnym razie ustaw ją na #, sprawdź każdego sąsiada mieszczącego się w granicach, używając i+1, przywróć ją i zwróć informację, czy którakolwiek próba zakończyła się powodzeniem.
Zwróć true, jeśli dfs zakończy się powodzeniem dla dowolnej komórki.

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

Pułapki i przypadki brzegowe

Nieodznaczenie komórki po nieudanej gałęzi: AAA na AA / AB daje wynik false.
Nieoznaczanie wcale: ścieżka cofa się na swoją ostatnią komórkę, a POP na przykładowej planszy zwraca true.
Odczytanie komórki przed sprawdzeniem granic: w Pythonie board[-1] to ostatni wiersz, więc ścieżki zawijają się wokół siatki.
Sprawdzanie sukcesu dopiero po wykonaniu ruchu: dla ["A"] z A musi zostać zwrócone true.
Oznaczanie przez zmianę wielkości liter w komórce: na ["aA"] oznaczone a jest odczytywane jako drugie A, więc aAA daje wynik true.

Najczęstsze pytania3

Jaka jest złożoność czasowa wyszukiwania słów?

O(m·n·3^L) dla planszy m × n i słowa o długości L: każda komórka może być początkiem ścieżki, a po pierwszym kroku każda komórka ma co najwyżej trzech nieodwiedzonych sąsiadów. Dodatkowa pamięć to O(L) na rekurencję oraz O(m·n) na kopię planszy.

Jak przycinanie przyspiesza wyszukiwanie słów?

Najpierw policz litery i zwróć false, jeśli na planszy jest za mało którejś z nich. Następnie rozpocznij wyszukiwanie od końca, używając rzadszej litery, od której może zaczynać się mniej pól. Żadne z tych sprawdzeń nie zmienia przypadku najgorszego.

Jaka jest różnica między Word Search a Word Search II?

Word Search II pyta, które słowa z listy występują na planszy. Wyszukiwanie każdego słowa osobno powtarza pracę, dlatego standardowe rozwiązanie umieszcza słowa w trie i przechodzi planszę raz, porzucając ścieżkę, gdy żadne słowo nie zaczyna się od jej liter.

def exist(board, word):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

true