class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
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))
results=deque()
word,lngth,word_isr='',0, False
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
ref=set()
for i in range(m):
for j in range(n-1):
ref.add(board[i][j]+board[i][j+1])
for j in range(n):
for i in range(m-1):
ref.add(board[i][j]+board[i+1][j])
def check(word):
for i in range(len(word)-1):
if word[i]+word[i+1] not in ref:
if word[i+1]+word[i] not in ref:
return False
return True
for w in words:
if check(w):
if w[:6]==w[0]*6 or len(dic[w[-1]])<len(dic[w[0]]):
word=w[::-1]
word_isr=True
else:
word=w
word_isr=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:break
return results
1. remove some string patterns that could never exist
2. dic - letter with cords
