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)
