Leetcode 79 Python для поиска слова решение, нужна помощь в отладке - PullRequest
Новая
       50

Leetcode 79 Python для поиска слова решение, нужна помощь в отладке

0 голосов
/ 11 декабря 2018

Я пытаюсь решить leetcode 79. поиск слова с помощью python, однако возникают проблемы с отладкой моего решения.Застрял в контрольном случае: {[["A", "B", "C", "E"], ["S", "F", "E", "S"], ["A", "D"," E "," E "]]" ABCESEEEFS "}, он не пройдет описанный выше тестовый пример, нужна помощь, спасибо. 

class Solution(object):
def exist(self, board, word):
    """
    :type board: List[List[str]]
    :type word: str
    :rtype: bool
    """

    def dfs(board, word, used, x, y):
        if not word: return True

        direction = [[0, 1],[0, -1],[1, 0],[-1, 0]]

        if (0 <= x < len(board)) and (0 <= y < len(board[0])) and ((x, y) not in used) and (board[x][y] == word[0]):

            used.add((x, y))                
            return (dfs(board, word[1:], used, x + direction[0][0], y + direction[0][1]) or 
                    dfs(board, word[1:], used, x + direction[1][0], y + direction[1][1]) or 
                    dfs(board, word[1:], used, x + direction[2][0], y + direction[2][1]) or 
                    dfs(board, word[1:], used, x + direction[3][0], y + direction[3][1]))

        return False



    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, word, set(), i, j) == True: return True

    return False

1 Ответ

0 голосов
/ 12 декабря 2018

Ваша проблема здесь в том, что когда вы передаете used в рекурсивный dfs, вы фактически передаете ссылку на функцию.То есть, когда вы начинаете с (0,0), затем переходите к (0,1) и т. Д., Вы могли бы потреблять (1,1), что появляется только позже в последовательности.

Другими словами, used будет содержать все ячейки доски задолго до предполагаемого поиска.

Чтобы исправить это, создайте клон used и перейдите к рекурсивному dfs: 

for dx,dy in direction:
    used_copy = set(used)
    used_copy.add((x,y))
    if dfs(board, word[1:], used_copy, x + dx, y + dy):
        return True
return False

Вы также можете удалить (x,y) после каждого рекурсивного вызова dfs, чтобы выне взрывай свою память: 

used.add((x,y))
for dx,dy in direction:
    if dfs(board, word[1:], used, x + dx, y + dy):
        return True

used.remove((x,y))
return False
...