#algorithm #recursion #backtracking
#алгоритм #рекурсия #отслеживание возврата
Вопрос:
Проблема: учитывая таблицу символов m x n и список строк words, верните все слова на доске.
Каждое слово должно быть построено из букв последовательно смежных ячеек, где соседние ячейки соседствуют по горизонтали или вертикали. Одна и та же буквенная ячейка не может использоваться более одного раза в слове. 
Вот мое решение:
class Solution(object):
def findWords(self, board, words):
WORD_KEY = '
Рекурсия всегда является моей самой большой проблемой, и трудно найти ошибку, я хочу знать, как я ошибаюсь в своем коде. Ниже приведен неправильный вывод:
["клятва", "клятва", "клятва", "клятва", "есть", "есть","есть","есть"], каждый повторяется 4 раза
вместо просто [клятва, ешь]
Комментарии:
1. было бы лучше, если бы вы также добавили сюда описание проблемы..
2. это кодовый номер 212, leetcode.com/problems/word-search-ii
3. @bot99zjc добавьте описание проблемы к вопросу, а не добавляйте к нему ссылку
4. @bot99zjc в вашей программе есть некоторые проблемы, в том числе последнее утверждение выявило проблему с форматированием. Пожалуйста, проверьте мой пересмотренный вариант в сообщении.
5. @DanielHao где именно проблема моего кода?
Ответ №1:
Это рабочий - он исправил некоторые проблемы в helper функции:
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] = '#' # marked as visited already
# Explore the neighbors in 4 directions
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 not board[newRow][newCol] in currNode:
continue
backtracking(newRow, newCol, currNode)
board[row][col] = letter # end of Exploration, restore it
#remove the matched leaf node in Trie.
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
trie = {}
for word in words:
node = trie
for letter in word:
# retrieve the next node; If not found, create a empty node.
node = node.setdefault(letter, {})
# mark the existence of a word in trie node
node[WORD_KEY] = word
rowNum = len(board)
colNum = len(board[0])
matchedWords = []
def helper(row,col,trie):
if trie.keys()[0]==WORD_KEY:
matchedWords.append(trie[WORD_KEY])
return
if row>len(board)-1 or row<0 or col>len(board[0])-1 or col<0:
return
if board[row][col] == '*':
return
if board[row][col] in trie:
for (rowOffset, colOffset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
temp=board[row][col]
board[row][col]='*'
helper(row rowOffset,col colOffset,trie[temp])
board[row][col]=temp
else:
return
for i in range(len(board)):
for j in range(len(board[0])):
helper(i,j,trie)
return matchedWords
Рекурсия всегда является моей самой большой проблемой, и трудно найти ошибку, я хочу знать, как я ошибаюсь в своем коде. Ниже приведен неправильный вывод:
[«клятва», «клятва», «клятва», «клятва», «есть», «есть»,»есть»,»есть»], каждый повторяется 4 раза
вместо просто [клятва, ешь]
Комментарии:
1. было бы лучше, если бы вы также добавили сюда описание проблемы..
2. это кодовый номер 212, leetcode.com/problems/word-search-ii
3. @bot99zjc добавьте описание проблемы к вопросу, а не добавляйте к нему ссылку
4. @bot99zjc в вашей программе есть некоторые проблемы, в том числе последнее утверждение выявило проблему с форматированием. Пожалуйста, проверьте мой пересмотренный вариант в сообщении.
5. @DanielHao где именно проблема моего кода?
Ответ №1:
Это рабочий — он исправил некоторые проблемы в helper функции: