第一版先来个爆搜的，对于每一个单词，先找找有没有跟第一个字母相等的，找到后开始向四周找这个单词。后来超时。
第二版，不是说做前缀树嘛，我就对那个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