Почему это работает
- Обход входит в клетку, только если у узла дерева есть потомок с её буквой, поэтому пройденный путь всегда — начало какого-то слова. Путь, с которого не начинается ни одно слово, сразу обрывается.
- Один обход работает на все слова сразу: у «ten» и «tea» общее «te», его проходим один раз, а каждое слово находится, когда обход доходит до узла, где оно лежит.
- Пометка # не даёт одному пути взять клетку дважды, а снятие пометки на обратном пути освобождает её для других путей. Убранное из узла слово не добавится второй раз, если его сложат два пути.
Сложность
Время O(m·n · 4 · 3^(L−1)) в худшем случае для сетки m×n и слов до L букв: обход стартует из каждой клетки, у первого шага 4 направления, у следующих — не больше 3. Дерево обычно обрывает это гораздо раньше. Память O(суммы длин слов) на дерево и O(L) на стек вызовов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗