第一版先來(lái)個(gè)爆搜的，對(duì)于每一個(gè)單詞，先找找有沒有跟第一個(gè)字母相等的，找到后開始向四周找這個(gè)單詞。后來(lái)超時(shí)。
第二版，不是說(shuō)做前綴樹嘛，我就對(duì)那個(gè)board做了個(gè)前綴樹。-_-||
比原來(lái)好一些，但還是超時(shí)。
第三版，難道是要把單詞構(gòu)造前綴樹？【不然嘞-_-||】但是之前的也別浪費(fèi)掉，也就是整了兩棵樹。構(gòu)造第二棵樹時(shí)，根據(jù)第一棵樹進(jìn)行剪枝?？傊峭ㄟ^(guò)了。
堅(jiān)持不看答案還是有收獲的
還是那句話，歡迎提意見

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