import numpy as np
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m,n=len(board),len(board[0])
dic=defaultdict(set)
for i in range(m):
for j in range(n):
dic[board[i][j]].add((i,j))
def dfs(cord,indx):
if indx==lngth:
# if word_isr:results.append(word[::-1])
# else:results.append(word)
return True
ch=word[indx]
i,j=cord
for cand in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if cand in dic[ch]:
dic[ch].remove(cand)
flag=dfs(cand,indx+1)
dic[ch].add(cand)
if flag:return True
return False
lngth=len(word)
for cord in list(dic[word[0]]):
dic[word[0]].remove(cord)
flag=dfs(cord,1)
dic[word[0]].add(cord)
if flag:return True
return False
how to store the location that previously visited
