Где применяется
1. Задача
У тебя есть сетка чисел. Правило простое: если в клетке стоит 0, то вся её строка и весь её столбец тоже должны стать 0. Один ноль превращает в нули целый крест.
Трудность в словах «на месте». Делать новую копию сетки под ответ нельзя. Надо менять ту сетку, которую тебе дали, и почти не тратить лишнюю память.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- существует ли слово как путь по доске
- проследить буквы через соседние клетки без повторов
- DFS с возвратом (backtracking) по сетке
- пометить клетку посещённой, затем отменить пометку
Похоже, но не то
- Бэктрекинг (Backtracking)
Это бэктрекинг по сетке вместо дерева. Варианты хода это четыре соседа.
- Обход графа BFS / DFS (Graph BFS / DFS)
Обход помечает клетку раз и навсегда. Здесь пометка снимается на выходе.
- Компоненты связности (Connected components)
Заливка тоже ходит по соседям, но пометки не снимает. Она считает, а не ищет.
- Trie (префиксное дерево) (Trie (prefix tree))
Когда слов много, trie обрезает обход. Без него каждое слово стоит своего поиска.
Сетка r на c и слово длины L стоят O(rc умножить на 4L). Работает это за счёт обрезки.
На LeetCode
Задачи на матрицу, где клетка меняет всю свою строку или столбец или где каждое новое значение зависит от старой сетки. Сначала запиши пометки, потом примени их вторым проходом, а если память должна быть O(1), бери строку 0 и столбец 0 как блокнот.
Задача урока слово в слово.
Сначала посчитай единицы в каждой строке и каждом столбце, и единица особая, когда оба её счётчика равны 1.
Посчитай единицы по строкам и столбцам за один проход, а вторым проходом заполни каждую клетку по двум счётчикам.
Каждая клетка меняется по старой сетке, поэтому пометь изменение на месте двумя лишними значениями, например 2 значит умирает, 3 значит рождается, и расшифруй их вторым проходом.