Поиск слов II: дерево префиксов и перебор с возвратом на сетке

«Поиск слов II» (LeetCode 212): дана доска символов размера m × n и список слов; необходимо найти все слова, которые можно составить из последовательно соседних клеток (по горизонтали или вертикали), причём каждую клетку можно использовать только один раз. Это сложнее, чем «Поиск слов I» (одно слово), поскольку необходимо одновременно найти все совпадающие слова — прямой запуск «Поиска слов I» для каждого слова имеет сложность O(W × m × n × 4^L), что слишком медленно.

Если вставить все целевые слова в префиксное дерево, а затем запустить поиск с возвратом на доске, можно искать все слова одновременно. Для каждой клетки доски вместо проверки «составляет ли этот путь моё целевое слово?» проверяется «соответствует ли этот путь префиксу в префиксном дереве?». Как только префикс в префиксном дереве перестаёт соответствовать, вся ветвь поиска с возвратом отсекается — это позволяет избежать повторной работы для всех слов с общим префиксом.

Вставьте все слова в префиксное дерево. Храните полное слово в конечном узле (в node.word), а не только логическое значение, чтобы при обнаружении полного совпадения во время поиска с возвратом можно было сразу добавить слово в результаты, не восстанавливая его посимвольно.

Запустите DFS из каждой клетки доски. На каждом шаге: (1) проверьте, существует ли символ текущей клетки среди дочерних узлов текущего узла префиксного дерева; (2) если да, отметьте клетку как посещённую (замените её специальным маркером, например '#') и рекурсивно обработайте 4 соседние клетки; (3) после рекурсии восстановите клетку (снимите отметку). Если у узла префиксного дерева значение word не равно None, добавьте его в результаты и присвойте ему None, чтобы избежать повторов (duplicates).

Время: O(m × n × 4^L), где L — максимальная длина слова. Для каждой из m×n начальных клеток DFS исследует до 4^L путей. Префиксное дерево отсекает пути, не соответствующие ни одному префиксу слова, поэтому на практике алгоритм работает намного быстрее. Построение префиксного дерева выполняется за O(W × L), где W — количество слов. Память: O(W × L) для префиксного дерева плюс O(L) для глубины стека рекурсии.

После нахождения слова удалите листовой узел из префиксного дерева (а не только обнулите слово), если у него нет дочерних узлов. Это предотвращает повторное посещение бесполезных ветвей в последующих вызовах DFS. Когда после нахождения слова дочерние узлы некоторого узла становятся недоступны, удалите этот узел из словаря дочерних узлов его родителя. Такая оптимизация особенно важна, когда многие слова имеют длинные общие префиксы.

Хранение полного слова в листовом узле префиксного дерева (вместо его восстановления по пути DFS) даёт два преимущества: (1) получение слова за O(1) при обнаружении совпадения вместо восстановления пути за O(L); (2) присваивание node.word = None после нахождения слова обеспечивает простое устранение повторов за O(1) без отдельного множества результатов. В частности, для «Поиска слов II» предотвращение повторов важно, поскольку одно и то же слово теоретически может быть найдено по разным путям.

Вместо отдельного множества visited (для которого потребовалось бы O(m × n) памяти на каждый путь DFS) помечайте клетки непосредственно на доске, заменяя их символ специальным маркером, например '#'. После возврата из DFS восстановите исходный символ. Этот приём: (1) использует O(1) дополнительной памяти на клетку; (2) автоматически предотвращает повторное посещение в рамках одного пути; (3) полностью прозрачен для обхода префиксного дерева, поскольку '#' никогда не встречается в нём.

Важные граничные случаи: (1) повторяющиеся слова в списке слов — сохраните слова в множестве или используйте приём node.word = None, чтобы предотвратить повторы в результатах; (2) очень длинные слова, превышающие размеры доски, — их нельзя составить, но DFS естественным образом обрабатывает этот случай, когда заканчиваются соседние клетки; (3) доска из одной клетки — можно найти только слова из одного символа; (4) одно и то же слово, которое можно найти по разным путям, — приём node.word = None предотвращает повторный подсчёт.

Наивный подход: для каждого из W слов запускать «Поиск слов I»: O(W × m × n × 4^L). С префиксным деревом все слова ищутся одновременно: O(m × n × 4^L) независимо от W. Для W=1000 слов длиной 10 на доске 10×10 наивный подход в 1000 раз медленнее префиксного дерева. Префиксное дерево действует как общий фильтр префиксов, распределяя затраты между всеми словами, — это классический пример использования структуры данных для достижения асимптотического улучшения.

Полное решение задачи «Поиск слов II»: постройте префиксное дерево по словам и храните строку слова в листе. Для каждой клетки доски запустите DFS: проверьте, существует ли текущий символ в текущем узле префиксного дерева, пометьте клетку символом '#', рекурсивно обработайте 4 соседние клетки и восстановите клетку. Если значение node.word не равно null, добавьте его в результаты и обнулите. При необходимости удаляйте пустые ветви префиксного дерева после использования. Верните список результатов. Время: O(m×n×4^L), память: O(W×L) для префиксного дерева + O(L) для рекурсии.

Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к техническому собеседованию», рассмотренных в этом уроке.

В этом уроке вы изучили следующее: «Поиск слов II» использует префиксное дерево для одновременного поиска нескольких слов с отсечением общих префиксов, хранение строки слова в листе префиксного дерева обеспечивает получение слова за O(1) и простое устранение повторов с помощью обнуления значения после нахождения, а также пометка посещённых клеток непосредственно на доске с помощью '#' позволяет избежать O(m×n) дополнительной памяти для каждого пути DFS. На этом курс «Префиксные деревья и алгоритмы работы со строками» завершён — вы освоили одну из самых мощных структур данных для работы со строками, используемых на собеседованиях.