Блог

В настоящее время я пытаюсь решить проблему поиска слов в leetcode. Вопрос заключается в следующем:

Учитывая сетку символов m x n и строковое слово, верните значение true, если слово существует в сетке.

Моя попытка заключается в следующем:

 class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def backtrack(loc: tuple, i: int) -> bool:
            x = loc[0]
            y = loc[1]
            if loc in seen:
                return False
            if  x >= len(board) or y >= len(board[0]):
                return False
            if 0 > x or 0 > y:
                return False
            if board[x][y] != word[i]:
                return False
            if i >= len(word)- 1:
                return True
            seen.add(loc)
            return backtrack((x 1, y), i 1) or backtrack((x-1, y), i 1) or backtrack((x, y-1), i 1) or backtrack((x,y 1), i 1)
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == word[0]:
                    seen = set()
                    if backtrack((i, j), 0):
                        return True
        return False
 

Теперь я могу решить проблему, если бы мне нужно было отредактировать ввод платы, чтобы проверить, посещалось ли состояние, но я бы предпочел не изменять входной массив, поэтому я решил использовать набор хэшей для этого. Однако я не могу должным образом реализовать проверку, и именно поэтому мой код не работает, поэтому я надеялся, что кто-нибудь сможет мне помочь. Спасибо!

Для алгоритмов обратного отслеживания вы должны вернуть сделанный вами «ход». Поэтому в этом случае вам придется удалить loc from seen после выполнения рекурсивных вызовов. Вот предлагаемое простое решение:

 class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def backtrack(loc: tuple, i: int) -> bool:
            x = loc[0]
            y = loc[1]
            if loc in seen:
                return False
            if  x >= len(board) or y >= len(board[0]):
                return False
            if 0 > x or 0 > y:
                return False
            if board[x][y] != word[i]:
                return False
            if i >= len(word)- 1:
                return True
            seen.add(loc)
            res = backtrack((x 1, y), i 1) or backtrack((x-1, y), i 1) or backtrack((x, y-1), i 1) or backtrack((x,y 1), i 1)
            seen.remove(loc)  # Removes loc from seen
            return res
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == word[0]:
                    seen = set()
                    if backtrack((i, j), 0):
                        return True
        return False