Leetcode79 单词搜索

题目描述

file

方法一

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(0,1),(0,-1),(1,0),(-1,0)]
    def traceback(i,j,k):
        if board[i][j] != word[k]:
            return False
        if k == len(word) - 1:
            return True
        visited.add((i,j))
        res = False
        for direct in directions:
            new_i, new_j = i + direct[0], j + direct[1]
            if 0 <= new_i < len(board) and 0 <= new_j < len(board[0]):
                if ((new_i,new_j)) not in visited:
                    if traceback(new_i,new_j,k+1):
                        res = True
                        break
        visited.remove((i,j))
        return res

    visited = set()
    for i in range(len(board)):
        for j in range(len(board[0])):
            if traceback(i,j,0):
                return True
    return False

 

思路

  • directions 存储方向
  • visited记录访问节点
  • 未采用的结果回溯 visited.remove()