Word Search: вернуть путь координат

MediumАлгоритмы
07:00
Лучше работает на десктопе
AlgorithmsDFSBacktrackingGrid
YouTube00:26:40-00:34:102025 11 10 21 03 18 Apriori Global Word Search [YouTube ySEvxRhzZ7M]Страница собеса

Дана таблица символов grid и строка word.

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

Одну и ту же клетку нельзя использовать дважды в одном пути.

Если путь не существует, верните None. Для пустой строки верните пустой путь [].

Сигнатура

def word_path(grid: list[list[str]], word: str):

Координаты возвращайте как список пар [row, col].

Примеры

Пример 1

Вход:
grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
Выход:[[0,0],[0,1],[0,2],[1,2],[2,2],[2,1]]

Пример 2

Вход:
grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "SEE"
Выход:[[1,3],[2,3],[2,2]]

Пример 3

Вход:
grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB"
Выход:null
Консоль
Нажмите Run или Ctrl+Enter для запуска