Где применяется
1. Задача
У тебя есть сетка букв и одно слово. Можно ли собрать это слово, если шагать по сетке на одну клетку за раз? Ходить можно только вверх, вниз, влево или вправо, по диагонали нельзя. На одну клетку нельзя вставать дважды. Ответь да или нет.
Сложность в том, что одна буква может стоять во многих местах, поэтому путей для проверки много. Нужен способ пробовать путь, а когда он заходит в тупик, отступать назад и пробовать другой.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитexist([["C", "A", "T", "S"], ["A", "X", "T", "O"], ["T", "O", "P", "S"]], "TOP")| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | C | A | T | S |
| 1 | A | X | T | O |
| 2 | T | O | P | S |
Можно ли пройти "TOP" по соседним клеткам доски, не беря ни одну клетку дважды? Пробуем начать с каждой клетки по очереди.
Как узнать
Эти слова в условии значат этот паттерн
- существует ли слово как путь по доске
- проследить буквы через соседние клетки без повторов
- DFS с возвратом (backtracking) по сетке
- пометить клетку посещённой, затем отменить пометку
Похоже, но не то
- Бэктрекинг (Backtracking)
Это бэктрекинг по сетке вместо дерева. Варианты хода это четыре соседа.
- Обход графа BFS / DFS (Graph BFS / DFS)
Обход помечает клетку раз и навсегда. Здесь пометка снимается на выходе.
- Компоненты связности (Connected components)
Заливка тоже ходит по соседям, но пометки не снимает. Она считает, а не ищет.
- Trie (префиксное дерево) (Trie (prefix tree))
Когда слов много, trie обрезает обход. Без него каждое слово стоит своего поиска.
Сетка r на c и слово длины L стоят O(rc умножить на 4L). Работает это за счёт обрезки.
На LeetCode
Задачи на сетку, где ищут путь по соседним клеткам без повторного захода в клетку, например чтобы составить слово или собрать больше всего золота. DFS помечает клетку, пробует четырёх соседей и возвращает клетку на выходе.
Задача урока слово в слово.
Запускай тот же DFS из каждой клетки с золотом и запоминай лучшую сумму. Золото лежит не больше чем в 25 клетках, так что это проходит.
Сначала посчитай пустые клетки, и путь засчитывается, только если он дошёл до конца, пройдя по всем.
Сложи слова в trie из урока 129, запусти один DFS из каждой клетки по trie и вырезай каждое найденное слово, как в уроке 130, чтобы поиск заканчивался раньше.