Word Search II: Trie i przeszukiwanie z nawrotami na siatce

Word Search II (LeetCode 212): dla planszy znaków o wymiarach m × n i listy słów należy znaleźć wszystkie słowa, które można utworzyć z kolejno sąsiadujących komórek (poziomo lub pionowo), przy czym każdej komórki można użyć tylko raz. Jest to trudniejsze niż Word Search I (jedno słowo), ponieważ trzeba znaleźć wszystkie pasujące słowa jednocześnie — naiwne uruchamianie Word Search I dla każdego słowa ma złożoność O(W × m × n × 4^L), co jest zbyt wolne.

Wstawienie wszystkich docelowych słów do trie, a następnie uruchomienie wyszukiwania DFS z nawrotami na planszy pozwala wyszukiwać wszystkie słowa jednocześnie. Dla każdej komórki planszy zamiast sprawdzać „czy ta ścieżka tworzy moje docelowe słowo?”, sprawdzamy „czy ta ścieżka odpowiada prefiksowi w trie?”. Gdy tylko prefiks w trie przestaje pasować, przycinamy całą gałąź DFS — unikając powtarzania pracy dla wszystkich słów współdzielących ten prefiks.

Wstawiamy wszystkie słowa do trie. Pełne słowo przechowujemy w węźle liścia (w node.word), a nie tylko wartość logiczną, aby po znalezieniu pełnego dopasowania podczas backtrackingu natychmiast dodać słowo do wyników bez odtwarzania go znak po znaku.

Uruchamiamy DFS z każdej komórki planszy. Na każdym kroku: (1) sprawdzamy, czy znak bieżącej komórki istnieje jako dziecko bieżącego węzła trie; (2) jeśli tak, oznaczamy komórkę jako odwiedzoną (ustawiamy w niej znacznik, taki jak '#') i wywołujemy rekurencję dla 4 sąsiadów; (3) po zakończeniu rekurencji przywracamy komórkę (usuwamy oznaczenie). Gdy węzeł trie ma niepustą wartość word, dodajemy ją do wyników i ustawiamy ją na None, aby uniknąć duplikatów.

Czas: O(m × n × 4^L), gdzie L to maksymalna długość słowa. Dla każdej z m×n komórek początkowych DFS przechodzi maksymalnie 4^L ścieżek. Trie przycina ścieżki, które nie odpowiadają żadnemu prefiksowi słowa, dlatego w praktyce rozwiązanie jest znacznie szybsze. Zbudowanie trie ma złożoność O(W × L), gdzie W to liczba słów. Pamięć: O(W × L) na trie oraz O(L) na głębokość stosu rekurencji.

Po znalezieniu słowa należy usunąć węzeł liścia z trie (a nie tylko wyzerować słowo), jeśli nie ma on dzieci. Zapobiega to ponownemu odwiedzaniu martwych gałęzi w kolejnych wywołaniach DFS. Gdy po znalezieniu słowa dzieci danego węzła zostaną usunięte, usuwamy ten węzeł ze słownika dzieci jego rodzica. Ta optymalizacja ma duże znaczenie, gdy wiele słów współdzieli długie prefiksy.

Przechowywanie pełnego słowa w liściu trie (zamiast odtwarzania go na podstawie ścieżki DFS) ma dwie zalety: (1) pobranie słowa po znalezieniu dopasowania zajmuje O(1), zamiast O(L) potrzebnego na odtworzenie ścieżki; (2) ustawienie node.word = None po znalezieniu słowa zapewnia proste usuwanie duplikatów w czasie O(1), bez potrzeby korzystania z osobnego zbioru wyników. W szczególności w Word Search II zapobieganie duplikatom jest istotne, ponieważ to samo słowo może teoretycznie zostać znalezione różnymi ścieżkami.

Zamiast osobnego zbioru visited (który wymagałby O(m × n) pamięci dla każdej ścieżki DFS) oznaczamy komórki w miejscu, zastępując ich znak znacznikiem, takim jak '#'. Po powrocie z DFS przywracamy oryginalny znak. Technika ta: (1) używa O(1) dodatkowej pamięci na komórkę; (2) automatycznie zapobiega ponownemu odwiedzeniu komórki w ramach jednej ścieżki; (3) jest całkowicie niewidoczna dla przechodzenia po trie, ponieważ '#' nigdy nie wystąpi w trie.

Ważne przypadki brzegowe: (1) zduplikowane słowa na liście słów — należy przechowywać je w zbiorze albo użyć sztuczki node.word = None, aby zapobiec duplikatom w wynikach; (2) bardzo długie słowa przekraczające wymiary planszy — nie można ich utworzyć, ale DFS naturalnie sobie z tym radzi, gdy zabraknie sąsiednich komórek; (3) plansza jednokomórkowa — można znaleźć tylko słowa składające się z jednego znaku; (4) to samo słowo możliwe do znalezienia różnymi ścieżkami — sztuczka node.word = None zapobiega wielokrotnemu zliczaniu.

Podejście naiwne: dla każdego z W słów uruchamiamy Word Search I, uzyskując O(W × m × n × 4^L). W przypadku trie wszystkie słowa są wyszukiwane jednocześnie: O(m × n × 4^L), niezależnie od W. Dla W=1000 słów o długości 10 na planszy 10×10 podejście naiwne jest 1000 razy wolniejsze niż rozwiązanie z trie. Trie działa jak współdzielony filtr prefiksów, który rozkłada koszt na wszystkie słowa — jest to klasyczny przykład wykorzystania struktury danych do uzyskania poprawy asymptotycznej.

Kompletne rozwiązanie Word Search II: budujemy trie ze słów i przechowujemy ciąg znaków słowa w liściu. Dla każdej komórki planszy uruchamiamy DFS: sprawdzamy, czy bieżący znak istnieje w bieżącym węźle trie, oznaczamy komórkę jako '#', wywołujemy rekurencję dla 4 sąsiadów i przywracamy komórkę. Gdy node.word nie ma wartości null, dodajemy słowo do wyników i ustawiamy je na null. Opcjonalnie po użyciu przycinamy puste gałęzie trie. Zwracamy listę wyników. Czas: O(m×n×4^L), pamięć: O(W×L) na trie + O(L) na rekurencję.

W tej lekcji omówiono: Word Search II wykorzystuje trie do jednoczesnego wyszukiwania wielu słów ze współdzielonym przycinaniem prefiksów, przechowywanie ciągu znaków słowa w liściu trie umożliwia pobranie słowa w czasie O(1) oraz łatwe usuwanie duplikatów przez ustawienie go na None po znalezieniu oraz oznaczanie odwiedzonych komórek w miejscu eliminuje potrzebę użycia O(m×n) dodatkowej pamięci dla każdej ścieżki DFS. W ten sposób kończy się kurs Tries and String Algorithms — opanowano jedną z najpotężniejszych struktur danych przeznaczonych do pracy z napisami, wykorzystywanych podczas rozmów technicznych.