Уровень сложности: Средняя (Medium)
Теги: Массив, Backtracking, Рекурсия, DFS (поиск в глубину)
Условие задачи
Дана двумерная доска символов board и строка word.
Верните true, если word существует на доске.
Слово существует, если его можно составить из букв последовательных соседних ячеек, где «соседние» — это горизонтально или вертикально прилегающие клетки.
Одну и ту же ячейку нельзя использовать дважды в одном слове.
Пример 1:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true
Пример 2:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Вывод: true
Пример 3:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Вывод: false
Объяснение: Путь требует повторного использования 'C', что запрещено.
Анализ задачи
Это задача на поиск пути в сетке с ограничением: нельзя посещать одну клетку дважды.
Главная идея — перебрать все возможные стартовые позиции, и для каждой запустить поиск в глубину (DFS) с backtracking.
💡 Как работает backtracking здесь?
- Найдём клетку, где первый символ слова совпадает с board[i][j].
- Отметим эту клетку как посещённую (чтобы не использовать дважды).
- Рекурсивно проверим четыре направления (вверх, вниз, влево, вправо) для следующего символа.
- Если рекурсия нашла слово — возвращаем true.
- Если нет — отменяем отметку (backtrack!) и пробуем другой путь.
Это классический DFS с временной маркировкой.
Решение на Java
Комментарии к коду:
- board[row][col] = '#' — временная метка «занято». Мы не создаём отдельный массив visited, а используем саму доску, что экономит память.
- Порядок проверок важен: сначала проверяем границы и совпадение, потом помечаем как посещённую.
- Backtrack обязателен: после рекурсии мы всегда возвращаем символ, чтобы другие ветки могли использовать эту клетку.
- Ранний выход: как только dfs возвращает true, мы сразу возвращаем true из основного метода.
💡 Это решение не нарушает входные данные в итоге, потому что все изменения откатываются.
Объяснение «словами пятилетнего»
Представь, у тебя есть магнитная доска с буквами, как в холодильнике:
A B C E
S F C S
A D E E
Ты хочешь найти слово «SEE».
Ты берёшь палец и начинаешь искать букву 'S'.
Нашёл! Ставишь на неё магнитик — «эта буква занята!»
Потом смотришь вокруг: есть ли рядом 'E'?
Есть! Ставишь второй магнитик на 'E'.
Смотришь снова вокруг: есть ли ещё 'E'?
Есть! Ставишь третий магнитик.
Слово найдено!
А теперь убираешь все магнитики, чтобы другие слова (например, «ABCCED») тоже могли использовать эти буквы.
Если в какой-то момент вокруг нет нужной буквы — ты убираешь последний магнитик и пробуешь другой путь.
Ты как детектив по буквам — пробуешь все тропинки, но никогда не используешь одну и ту же букву дважды в одном слове!
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task79_wordSearch/Solution.java