leetcode 单词搜索 II python
2019-03-23 本文已影响0人
DaydayHoliday
第一版先来个爆搜的,对于每一个单词,先找找有没有跟第一个字母相等的,找到后开始向四周找这个单词。后来超时。
第二版,不是说做前缀树嘛,我就对那个board做了个前缀树。-_-||
比原来好一些,但还是超时。
第三版,难道是要把单词构造前缀树?【不然嘞-_-||】但是之前的也别浪费掉,也就是整了两棵树。构造第二棵树时,根据第一棵树进行剪枝。总之是通过了。
坚持不看答案还是有收获的
还是那句话,欢迎提意见
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
words=set(words)
if len(words)==0:
return []
self.geneWordTri(words)
res=[]
self.board=board
self.rownum=len(board)
self.colnum=len(board[0])
self.wordDict={}
self.maxLen=max(map(len,words))
self.geneDict()
for word in words:
if self.check(word):
res.append(word)
return res
def geneWordTri(self,words):
wordTree={}
for word in words:
curTree=wordTree
for wi in word:
if wi not in curTree:
curTree[wi]={}
curTree=curTree[wi]
self.wordTree=wordTree
def check(self, word):
curDict=self.wordDict
for i in word:
if i in curDict:
curDict=curDict[i]
else:
return False
return True
def geneDict(self):
visited=[[False]*self.colnum for r in range(self.rownum)]
for i in range(self.rownum):
for j in range(self.colnum):
if self.board[i][j] not in self.wordTree:
continue
visited[i][j]=True
if self.board[i][j] not in self.wordDict:
self.wordDict[self.board[i][j]]={}
self.fillDict(i,j,visited,self.wordDict[self.board[i][j]],self.wordTree[self.board[i][j]],1)
visited[i][j]=False
def fillDict(self,i,j,visited,curDict,curTree,dictLen):
if dictLen>=self.maxLen:
return
nextStep=[[i+1,j],[i-1,j],[i,j+1],[i,j-1]]
for step in nextStep:
if step[0]<0 or step[1]<0 or step[0]>=self.rownum or step[1]>=self.colnum or visited[step[0]][step[1]]:
continue
if self.board[step[0]][step[1]] not in curTree:
continue
visited[step[0]][step[1]]=True
if self.board[step[0]][step[1]] not in curDict:
curDict[self.board[step[0]][step[1]]]={}
self.fillDict(step[0],step[1],visited,curDict[self.board[step[0]][step[1]]],curTree[self.board[step[0]][step[1]]],dictLen+1)
visited[step[0]][step[1]]=False