word-Search-II(路径查找)

https://leetcode.com/problems/word-search-ii/

原先直接搜索和查找的方式到34个case的时候就超时了，一共偶36个case. 后面采用Trie(字典树的形式实现对前缀树的一次性查找避免多次查找耗费时间)

问题：

Given a 2D board and a list of words from the dictionary, find all words in the board. 
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. 
The same letter cell may not be used more than once in a word.

示例1：

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output:
 ["eat","oath"]

示例2：

Input:
board = [["a","b"],["a","a"]]
words = ["aba","baa","bab","aaab","aaa","aaaa","aaba"]

Output:
['aaab', 'aaba', 'baa', 'aba', 'aaa']

import heapq
from typing import *
import functools
import copy
from collections import defaultdict

class Trie:
   def __init__(self):
       self.children = {}
       self.is_word = False
       self.word = None


class Solution: 
   def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
       
       
       length = len(board)
       size = len(board[0])
       
       if not board or not board[0] or not words:
           return []
       
       
       def makeTrie(words):
           trie = Trie()

           for word in words:
               point = trie
               for index, letter in enumerate(word):
                   
                   if not letter in point.children:
                       point.children[letter] = Trie()
                   
                   
                   
                   point = point.children[letter]
                   if index == len(word) - 1:
                       point.is_word = True
                       point.word = word
                   
           return trie
       root = makeTrie(words)
       result = set()
       
       def isOutRange(x,y):
           if x>=0 and x<length and y>=0 and y< size:
               return False
           else:
               return True
       
       
       def isTrue(i, j, final, visited, tree):
           
  
           
           if tree.is_word:
               final.add(tree.word)
           
           visited.add((i,j))
           
           
           
           nextVisited = [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
           for n in nextVisited:
               if not n in visited and not isOutRange(n[0],n[1]) and board[n[0]][n[1]] in tree.children:
                   isTrue(n[0], n[1], final, visited, tree.children[board[n[0]][n[1]]])
           
           visited.remove((i,j))
           

       for i in range(length):
           for j in range(size):
               if board[i][j] in root.children:
                   isTrue(i,j,result,set(),root.children[board[i][j]])
       
       return list(result)