Word Search

Q: Czym jest złożoność czasowa wyszukiwania słowa?

Najgorszy przypadek to O(m·n·3^L) dla planszy m × n i słowa o długości L . Każda z m·n komórek może być początkiem ścieżki, a po pierwszym kroku każda komórka ma najwyżej trzech nieodwiedzonych sąsiadów do sprawdzenia. Dodatkowe miejsce wynosi O(L) na rekurencję oraz O(m·n) , jeśli kopiujesz planszę, aby ją oznaczyć.

ŚrednieNawroty Grafy

+10

Otrzymujesz siatkę liter board, podaną jako 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 prześledzić word na siatce: zacznij w dowolnej komórce, a następnie za każdym razem przejdź do komórki bezpośrednio nad, pod, po lewej lub po prawej stronie bieżącej komórki, tak aby odwiedzane komórki układały się w word we właściwej kolejności. Podczas śledzenia nie można użyć tej samej komórki dwa razy. W przeciwnym razie zwróć false. Wielkość liter ma znaczenie, więc a i A to różne litery.

Funkcja

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

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

Ograniczenia

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, a każdy wiersz ma taką samą długość.
1 ≤ word.length ≤ 20
board i word zawierają wyłącznie litery alfabetu angielskiego — wielkie i małe.

Przykłady

Wejście: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Wyjście: true
Wyjaśnienie: Zacznij na S w wierszu 0, kolumnie 0, następnie przejdź w prawo do T, w dół do O, w prawo do drugiego O, w prawo do L, a potem w dół do S w wierszu 2, kolumnie 3. To sześć różnych komórek, z których każda sąsiaduje z poprzednią.

Wejście: board = ["STAR", "POOL", "ENDS"]word = "POP"
Wyjście: false
Wyjaśnienie: Na planszy znajduje się tylko jedno P, w wierszu 1, kolumnie 0. Po P i O potrzebujesz kolejnego P, a jedyne takie pole to to, od którego zaczęła się ścieżka, a 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 ścieżka urywa się już na pierwszym kroku: jedyne A znajduje się w wierszu 0, kolumnie 2, a żadna z liter S go nie dotyka.

+23 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Zamiast odpowiedzi „tak” lub „nie” możesz policzyć, ile różnych ścieżek word zawiera plansza?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Żaden wzór nie daje odpowiedzi: musisz przeszukać ścieżki na planszy. Backtracking robi to, sprawdzając jedną ścieżkę naraz. Wydłużasz ścieżkę o jedną literę, oznaczasz każde pole, gdy ścieżka z niego korzysta, i odznaczasz je, gdy się cofasz, dzięki czemu w obrębie jednej ścieżki pole nigdy nie jest używane ponownie, ale pozostaje dostępne dla każdej innej ścieżki. W najgorszym przypadku czas działania tego przeszukiwania rośnie wykładniczo wraz z długością słowa, co jest w porządku na planszy o wymiarach najwyżej 6 × 6. Dwie proste kontrole przed rozpoczęciem — zliczenie liter i rozpoczęcie od rzadszego końca słowa — często ograniczają liczbę kroków z dziesiątek tysięcy do kilkudziesięciu.

Backtracking z użyciem siatki odwiedzonych pól

Intuicja

Wyobraź sobie drzewo decyzji. Pierwszy wybór to pole startowe i musi zawierać word[0]. Potem każdy węzeł reprezentuje ścieżkę, która tworzy pierwsze i liter, a jego dziećmi są sąsiednie pola zawierające word[i], które nie znajdują się jeszcze na ścieżce. Ścieżka tworząca całe słowo oznacza sukces. Ścieżka bez takiego sąsiada prowadzi donikąd, więc cofasz się, aby spróbować kolejnego wyboru.

Tablica visited wymusza zasadę jednorazowego użycia pola. Oznacz pole, gdy ścieżka na nie wchodzi, i odznacz je, gdy z niego schodzi. To odznaczanie sprawia, że jest to przeszukiwanie z nawrotami: pole, przez które przebiegała ścieżka prowadząca donikąd, musi znów być dostępne przy kolejnej próbie. Na planszy AA / AB ze słowem AAA, zaczynając od pola w lewym górnym rogu, ruch w dół kończy się na polu w lewym dolnym rogu (jego drugim sąsiadem jest B), a ruch w prawo kończy się na polu w prawym górnym rogu. Gdyby te pola pozostały oznaczone, nie dałoby się znaleźć odpowiedzi: lewy dolny róg, potem lewy górny róg, a następnie prawy górny róg.

To standardowe rozwiązanie, które jest poprawne i wystarczająco szybkie w tym przypadku. Jego koszt zależy od liczby przeszukiwanych ścieżek. Po pierwszym ruchu każdy krok ma najwyżej trzy nowe kierunki, więc słowo złożone z L liter może oznaczać około m·n·3^L ścieżek. Weź planszę 5 × 5 wypełnioną literą A i słowo złożone z 8 liter A, po których następuje B. Każda ścieżka złożona z liter A jest poprawnym prefiksem, więc przeszukiwanie sprawdza je wszystkie, zanim odkryje, że nie ma żadnego B: około 65 000 sprawdzeń pól, aby zwrócić false. Każda dodatkowa litera mniej więcej podwaja tę liczbę, dlatego w kolejnym podejściu przed rozpoczęciem przeszukiwania sprawdzamy kilka rzeczy.

Algorytm

Utwórz tablicę visited o rozmiarze planszy, wypełnioną wartościami false.
Zdefiniuj dfs(r, c, i): zwróć false, jeśli (r, c) znajduje się poza siatką, jest odwiedzone lub jego litera nie jest równa word[i].
Jeśli i jest ostatnim indeksem word, zwróć true.
Oznacz (r, c) jako odwiedzone, sprawdź czterech sąsiadów z i+1, a następnie usuń to oznaczenie i zwróć informację, czy którykolwiek z sąsiadów zakończył się powodzeniem.
Wywołaj dfs(r, c, 0) dla każdej komórki i zwróć true, gdy tylko jedno wywołanie zakończy się powodzeniem.

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 wykorzystaniem znaczników w miejscu i przycinania

Intuicja

Zachowaj to samo wyszukiwanie i wprowadź dwie zmiany. Po pierwsze, oznaczaj komórki na prywatnej kopii planszy zamiast w osobnej siatce: nadpisuj komórkę znakiem #, gdy ścieżka z niej korzysta, a podczas cofania przywracaj literę. # nigdy nie jest równe żadnej literze słowa, więc sprawdzanie liter odrzuca też komórki należące do ścieżki, a przywracanie jest tym samym krokiem cofania co wcześniej.

Po drugie, przycinaj wyszukiwanie, zanim je rozpoczniesz. Policz litery. Jeśli słowo wymaga więcej wystąpień jakiejś litery, niż jest ich na planszy, odpowiedzią jest false i nie trzeba niczego wyszukiwać. To pozwala od razu rozstrzygnąć przypadek planszy z samymi A — 8 literami A i literą B — bez żadnego wyszukiwania, zamiast wykonywać około 65,000 sprawdzeń. Zacznij od rzadszego końca. Ścieżka odczytana od tyłu tworzy odwrócone słowo na tych samych komórkach, więc możesz wyszukiwać odwróconego słowa. Jeśli ostatnia litera występuje na planszy rzadziej niż pierwsza, odwróć słowo. Wyszukiwanie może się rozpocząć z mniejszej liczby komórek, a rzadka litera eliminuje błędne początki już w pierwszym kroku, zamiast w ostatnim.

Druga zasada ma znaczenie, gdy rzadka litera występuje na planszy, ale jest poza zasięgiem. Umieść jedyną literę B w rogu, którego dwaj sąsiedzi to C, i wyszukuj słowa złożonego z 8 liter A, po których następuje B. Test liczby liter przechodzi. Przy wyszukiwaniu od przodu algorytm nadal przechodzi przez każdą ścieżkę liter A, wykonując około 35,000 sprawdzeń komórek. Przy wyszukiwaniu od tyłu słowo zaczyna się od B, tylko jedna komórka może być początkiem, a jej sąsiadami nie są litery A, więc wyszukiwanie kończy się po około 30 sprawdzeniach.

Najgorszy przypadek nadal ma złożoność O(m·n·3^L): można zbudować planszę i słowo, w których litery występują w równych proporcjach, a ślepe zaułki pojawiają się późno. Przycinanie nie zmienia odpowiedzi ani granicy złożoności. Eliminuje typowe przyczyny marnowania czasu przez proste wyszukiwanie, kosztem jednego przebiegu zliczającego litery, a korzyści szybko rosną wraz z długością słowa.

Algorytm

Policz każdą literę na planszy i w słowie. Jeśli słowo wymaga więcej wystąpień którejś litery, niż jest ich na planszy, zwróć false.
Jeśli na planszy jest więcej wystąpień word[0] niż ostatniej litery, odwróć word.
Skopiuj planszę do siatki znaków, którą możesz modyfikować.
Zdefiniuj dfs(r, c, i): zakończ niepowodzeniem, jeśli komórka nie zawiera word[i]; zakończ powodzeniem, jeśli i jest ostatnim indeksem; w przeciwnym razie ustaw komórkę na #, sprawdź każdego sąsiada mieszczącego się w granicach, używając i+1, przywróć literę i zwróć informację, czy któreś wywołanie zakończyło się powodzeniem.
Uruchom dfs(r, c, 0) dla każdej komórki i zwróć true, gdy tylko jedno wywołanie zakończy się powodzeniem.

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

Większość błędnych odpowiedzi wynika z oznaczania komórek i sprawdzania granic.

Nieodznaczanie komórki po nieudanej gałęzi. Komórka pozostaje zablokowana dla każdej późniejszej ścieżki, a dla AA / AB słowo AAA daje wynik false.
Całkowity brak oznaczania. Bez tego ścieżka może wrócić do komórki, z której przyszła, a POP na przykładowej planszy zwróciłoby true.
Odczytywanie komórki przed sprawdzeniem granic. W Pythonie board[-1] to ostatni wiersz, a nie błąd, więc brak sprawdzenia granic po cichu powoduje zawijanie się na drugą stronę siatki.
Sprawdzanie powodzenia dopiero po wykonaniu ruchu. Słowo jednoliterowe na planszy złożonej z jednej komórki, ["A"] z A, musi zwrócić true, mimo że komórka nie ma sąsiadów.
Oznaczanie znakiem, który może być prawdziwą literą. Na przykład zmiana wielkości litery w komórce powoduje błędy na planszach, na których występują zarówno a, jak i A.
Poruszanie się po przekątnej. Za sąsiadów uznaje się tylko cztery komórki, które mają wspólny bok.

Najczęstsze pytania4

Czym jest złożoność czasowa wyszukiwania słowa?

Najgorszy przypadek to O(m·n·3^L) dla planszy m × n i słowa o długości L. Każda z m·n komórek może być początkiem ścieżki, a po pierwszym kroku każda komórka ma najwyżej trzech nieodwiedzonych sąsiadów do sprawdzenia. Dodatkowe miejsce wynosi O(L) na rekurencję oraz O(m·n), jeśli kopiujesz planszę, aby ją oznaczyć.

Dlaczego odznaczasz pola w wykreślance?

Znacznik oznacza, że komórka znajduje się na bieżącej ścieżce. Gdy gałąź zawodzi, komórka opuszcza ścieżkę i może być potrzebna na innej ścieżce. Jeśli pozostawisz znacznik, kolejne wyszukiwania będą traktować komórkę jako używaną i mogą nie znaleźć poprawnego rozwiązania. Oznaczaj komórkę przy wejściu, a usuwaj oznaczenie przy wyjściu.

Jak przycinanie przyspiesza wyszukiwanie słów?

Przed rozpoczęciem wyszukiwania wykonywane są dwie kontrole. Jeśli słowo wymaga większej liczby wystąpień którejś litery, niż znajduje się na planszy, możesz zwrócić false bez wyszukiwania. Ponieważ ścieżka odczytana od końca tworzy odwrócone słowo, możesz też zacząć od tego końca, przy którym znajduje się rzadsza litera. Dzięki temu zmniejsza się liczba pól startowych i szybciej odrzucane są nieprawidłowe ścieżki. Żadna z tych zmian nie wpływa na przypadek pesymistyczny, a samo wyszukiwanie jest już kompletnym rozwiązaniem. Na planszy 5 × 5 z literami A i słowie, które wymaga brakującej litery B, pozwalają zmniejszyć liczbę sprawdzanych pól z około 65 000 do zera.

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

Word Search pyta o jedno słowo. Word Search II podaje listę słów i pyta, które z nich występują na planszy. Wykonywanie wyszukiwania osobno dla każdego słowa powtarza wiele pracy, dlatego typowe rozwiązanie umieszcza wszystkie słowa w drzewie trie i przechodzi planszę jeden raz, porzucając ścieżkę, gdy tylko okaże się, że żadne słowo nie zaczyna się od jej liter.

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

true