Сложность: hard
Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.
Каждое слово должно быть составлено из букв последовательных смежных ячеек, где смежные ячейки находятся по горизонтали или вертикали рядом. Одна и та же ячейка с буквой не может использоваться более одного раза в слове.
Пример:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
👨💻 Алгоритм:
1️⃣ Построение Trie:
Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.
2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).
3️⃣ Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.
😎 Решение:
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
WORD_KEY = "$"
trie = {}
for word in words:
node = trie
for letter in word:
node = node.setdefault(letter, {})
node[WORD_KEY] = word
rowNum = len(board)
colNum = len(board[0])
matchedWords = []
def backtracking(row, col, parent):
letter = board[row][col]
currNode = parent[letter]
word_match = currNode.pop(WORD_KEY, False)
if word_match:
matchedWords.append(word_match)
board[row][col] = "#"
for rowOffset, colOffset in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
newRow, newCol = row + rowOffset, col + colOffset
if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
continue
if board[newRow][newCol] not in currNode:
continue
backtracking(newRow, newCol, currNode)
board[row][col] = letter
if not currNode:
parent.pop(letter)
for row in range(rowNum):
for col in range(colNum):
if board[row][col] in trie:
backtracking(row, col, trie)
return matchedWords
Ставь 👍 и забирай 📚 Базу знаний