Почему это работает
- Вызов отвечает на один вопрос: можно ли прочитать word[k:], начиная с этой клетки? Его буква должна совпасть, а потом кто-то из соседей должен ответить «да» про word[k + 1:], поэтому true наверху означает настоящий путь.
- Пока клетка на пути, в ней стоит #, который не совпадает ни с одной буквой, поэтому вызов, вернувшийся в неё, сам себе отказывает: ни одна клетка не читается дважды.
- Каждый вызов возвращает свою букву на место перед возвратом, поэтому тупик оставляет доску такой, какой её застал, и клетка свободна для других путей.
Сложность
Время O(m × n × 3ᴸ), где L — длина слова: путь может начаться в любой из m × n клеток, а после первого шага у клетки не больше 3 соседей, кроме той, откуда пришли. Память O(L): стек вызовов не глубже L, а пометки живут на самой доске.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗