当前位置: 首页 > 后端技术 > Python

leetcode79.查词wordsearch

时间:2023-03-26 15:02:49 Python

https://leetcode-cn.com/probl...解题思路可以在每个点上下左右四个方向进行搜索。但是注意不能回到已经搜索过的地方,所以定义了mp记录是否所有的点都搜索过。否则如:[['A','B']],'ABA'[['A','B'],['D','C']]'ABCDA'被认为是True可以看到搜索过程的具体例子:[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]],"ABCESEEEFS"00A01B02C03E13S12E22E23Ebacktrackbacktrackbacktrack23E22E12E11F10S从左上开始沿着第一行到右上,然后到第二行最右边的S。这时候不是继续往下走,而是先往左走,导致后面搜索3个E的,你在角落里,所以这里有个回溯,回退三步,还是回这个S,和从这里往下走就能找到最终答案。代码类解决方案:defexist(self,board:List[List[str]],word:str)->bool:n=len(board)m=len(board[0])defdfs(i,j,index):mp[i][j]=False#print('\t'*index,i,j,word[index-1])ifindex==len(word):returnTrueforii,jjin[(0,1),(0,-1),(1,0),(-1,0)]:如果0<=i+ii