Word Search II

Сложная№212дерево и сетка вместе

Есть сетка букв и список слов. Нужно вернуть все слова, которые складываются по пути из клеток, соседних сверху, снизу, слева или справа, причём в одном слове клетка берётся не больше одного раза. Наш пример: сетка tea / ons и слова toe, tea, ten — ответ [ten, tea]; «toe» на доске нет.

212 Word Search IIРазбор · 1×

Пример: сетка tea / ons и слова toe, tea, ten. Дерево справа идёт вместе с обходом: двойное кольцо — ещё не найденное слово.

01201teaonsteoanerootнайдено—
свободная клетка; узел вне обходана пути: клетка с #, её узелтекущий вызовсосед, куда идёт обходсосед, которым не продолжается ни одно словослово найдено

Кладём «toe», «tea», «ten» в префиксное дерево, как на карточке; каждое слово хранится в своём последнем узле (двойное кольцо)

01/50
сначала · назад · пуск · шаг
Скорость
1function findWords(board, words):
2 root = trie of words // word kept on its end node
3 found = []
4 for each cell (r, c) of board:
5 if board[r][c] in root.children:
6 dfs(r, c, root.children[board[r][c]])
7 return found
8function dfs(r, c, node):
9 if node.word is not none:
10 add node.word to found
11 node.word = none // never added twice
12 ch = board[r][c]
13 board[r][c] = '#'
14 for each neighbour (nr, nc) of (r, c):
15 if board[nr][nc] in node.children:
16 dfs(nr, nc, node.children[board[nr][nc]])
17 board[r][c] = ch
состояние
found
[]
r
–
c
–
node
–
ch
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Обход входит в клетку, только если у узла дерева есть потомок с её буквой, поэтому пройденный путь всегда — начало какого-то слова. Путь, с которого не начинается ни одно слово, сразу обрывается.
  2. Один обход работает на все слова сразу: у «ten» и «tea» общее «te», его проходим один раз, а каждое слово находится, когда обход доходит до узла, где оно лежит.
  3. Пометка # не даёт одному пути взять клетку дважды, а снятие пометки на обратном пути освобождает её для других путей. Убранное из узла слово не добавится второй раз, если его сложат два пути.

Сложность

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

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.