【leetcode25】

作者

79. 单词搜索

  1. class Solution:
  2.     def exist(self, board: List[List[str]], word: str) -> bool:
  3.         rows,cols=len(board),len(board[0])
  4.         direct=[(0,1),(0,-1),(1,0),(-1,0)]
  5.         visted=[[False]*cols for _ in range(rows)]
  6.         def f(l,r,index):
  7.             if(len(word)==index):
  8.                 return True
  9.             if l<0 or l>=rows or r<0 or r>=cols or visted[l][r] or board[l][r]!=word[index]:
  10.                 return False
  11.             visted[l][r]=True
  12.             for dl,dr in direct:
  13.                 if f(l+dl,r+dr,index+1):
  14.                     return True
  15.             visted[l][r]=False
  16.             return False
  17.         for i in range(rows):
  18.             for j in range(cols):
  19.                 if f(i,j,0):
  20.                     return True
  21.         return False
披着回溯皮的深搜

发表评论