Алгоритмическая секция в Apriori Global

Тип тренировки

Алгоритмы

Задач

Компания

Apriori Global

Дата

2025-11-10

Задача 1MediumDFSБэктрекингСетка

Word Search в таблице символов

Дана таблица символов grid и строка word . Нужно определить, можно ли собрать word, двигаясь по соседним клеткам вверх, вниз, влево или вправо. Одну и ту же клетку нельзя использовать дважды в одном пути.

def word_exists(grid: list[list[str]], word: str) -> bool:

Консоль

Нажмите «Запустить проверки» или Ctrl+Enter

Запускаем DFS из каждой клетки, которая совпадает с первым символом. В DFS проверяем текущий символ, помечаем клетку как использованную, рекурсивно пробуем четыре направления и снимаем пометку при откате. Backtracking нужен, потому что одна клетка может участвовать в разных кандидатных путях, но не может повторяться внутри одного пути.

Оцените сложность

По времени

По памяти

Задача 2MediumDFSБэктрекингСетка

Дана таблица символов grid и строка word . Нужно вернуть один путь координат, по которому можно собрать word, двигаясь вверх, вниз, влево или вправо. Одну и ту же клетку нельзя использовать дважды в одном пути. Если путь не существует, верните None . Для пустой строки верните пустой путь [] .

def word_path(grid: list[list[str]], word: str): Координаты возвращайте как список пар [row, col] .

Консоль

Нажмите «Запустить проверки» или Ctrl+Enter

Это та же DFS/backtracking задача, что и проверка существования пути, но теперь нужно хранить текущий путь. При входе в клетку добавляем [r, c] в path и помечаем клетку как visited. Если дальше путь не найден, снимаем visited и удаляем последнюю координату. Когда индекс дошел до длины слова, возвращаем копию path .

Оцените сложность

По времени

По памяти