Поиск слова
Дана двумерная сетка символов board и строка word. Верните true, если слово присутствует в сетке, иначе верните false.
Слово считается присутствующим, если его можно составить, двигаясь по соседним ячейкам сетки по горизонтали или вертикали. Одну и ту же ячейку нельзя использовать более одного раза при составлении слова.
Пример 1:
Input:
board = [
["A","B","C","D"],
["S","A","A","T"],
["A","C","A","E"]
],
word = "CAT"
Output: true
Рекомендуемая временная и пространственная сложность
Временная сложность: O(N * M * 4^L), где N и M - размеры сетки, L - длина слова. Пространственная сложность: O(L), где L - длина слова.
Подсказка 1
Попробуйте использовать поиск с возвратом (backtracking). Начните с поиска первой буквы слова в сетке.
Подсказка 2
После нахождения первой буквы, исследуйте все возможные пути, двигаясь в четырех направлениях (вверх, вниз, влево, вправо).
Подсказка 3
Используйте дополнительную структуру данных (например, множество) для отслеживания уже посещенных ячеек, чтобы не использовать их повторно.