Word Search

Средняя№79путь по сетке

Дана доска с буквами и слово. Нужно сказать, можно ли прочитать слово по пути из клеток, где каждая следующая клетка соседствует с предыдущей сверху, снизу, слева или справа, а ни одна клетка не берётся дважды. Наш пример: доска TE / OT / TO и слово TOTE → true.

79 Word SearchРазбор · 1×

Пример: доска TE / OT / TO (строки сверху вниз) и TOTE. Смотрите на (0, 0), когда путь просит у неё вторую T: там стоит T, но клетка помечена #, ведь путь начался в ней.

01012TEOTTOслово0T1O2T3E
свободная клеткана пути, помечена #клетка этого вызова, буква совпалаотказ: не та буква или #тупик, буква возвращенанайденный путь

Можно ли прочитать TOTE по пути из соседних клеток, беря каждую клетку один раз?

01/41
сначала · назад · пуск · шаг
Скорость
1function exist(board, word):
2 for each cell of board:
3 if found(cell, 0):
4 return true
5 return false
6
7function found(cell, k):
8 if board[cell] != word[k]: return false
9 if k == len(word) - 1: return true
10 board[cell] = '#' // in use: no second visit
11 ok = any(found(n, k + 1) for n in around(cell))
12 board[cell] = word[k] // free it for other paths
13 return ok
состояние
cell
–
k
–
n
–
ok
–
нажмите шаг, чтобы вернуться

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

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

  1. Вызов отвечает на один вопрос: можно ли прочитать word[k:], начиная с этой клетки? Его буква должна совпасть, а потом кто-то из соседей должен ответить «да» про word[k + 1:], поэтому true наверху означает настоящий путь.
  2. Пока клетка на пути, в ней стоит #, который не совпадает ни с одной буквой, поэтому вызов, вернувшийся в неё, сам себе отказывает: ни одна клетка не читается дважды.
  3. Каждый вызов возвращает свою букву на место перед возвратом, поэтому тупик оставляет доску такой, какой её застал, и клетка свободна для других путей.

Сложность

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

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

Решить на LeetCode ↗

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