Trie 树

字典树，建立init 就是把一个个单词塞进去。
功能有查找完整的，和查找前缀的，提供两个模板。
使用场景有前缀树和后缀树两种使用。

长模板：

便于理解，看了代码一看就理解的。
apple:{‘a’: {‘p’: {‘p’: {‘l’: {‘e’: {‘end’: True}}}}}} #第一次insert，最后一个’e’存在结束’end’
app: {‘a’: {‘p’: {‘p’: {‘l’: {‘e’: {‘end’: True}}, ‘end’: True}}}} #第二次insert，第二个’p’存在结束’end’

class Trie:
    def __init__(self):
        self.tree={}
    def insert(self, word: str) -> None:
        t=self.tree
        for char in word:
            if char not in t:
                t[char]={}
            t=t[char]
        t["end"]=True        
    def search(self, word: str) -> bool:
        t=self.tree
        for char in word:
            if char not in t:
                return False
            t=t[char]
        return "end" in t
    def startsWith(self, prefix: str) -> bool:
        t=self.tree
        for char in prefix:
            if char not in t:
                return False
            t=t[char]
        return True

短模板

便于抄写，都是高端python写法，reduce 和defaultdict，不展开了。

from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
    def __init__(self):
        self.trie = TrieNode()
    def insert(self, word):
        reduce(dict.__getitem__, word, self.trie)['end'] = True
    def search(self, word):
        return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
    def startsWith(self, word):
        return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())

例题：

一般Trie 都是要继续迭代node的。
所以Trie类光会抄模板也不一定有用，要理解现在的node是什么，该怎么用，要不要从头开始遍历tree

212. 单词搜索 II

from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
    def __init__(self):
        self.trie = TrieNode()
    def insert(self, word):
        reduce(dict.__getitem__, word, self.trie)['end'] = True
    def search(self, word):
        return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
    def startsWith(self, word):
        return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0]:return []
        m,n=len(board),len(board[0])
        self.tree=Trie()   
        self.ans=[]
        for word in words:
            self.tree.insert(word)
        directions =[(1,0),(-1,0),(0,1),(0,-1)]
        def dfs(i,j,t,s):
            if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j] not in t: return
            char=board[i][j]
            path = s+char
            board[i][j]="#"
            if "end" in t[char]:
               self.ans.append(path)
            for ix,iy in directions:
                x,y=i+ix,j+iy
                dfs(x,y,t[char],path)
            board[i][j]=char
        for i in range(m):
            for j in range(n):
                t=self.tree
                dfs(i,j,t.trie,"")
        return list(set(self.ans))

820. 单词的压缩编码

解法1：建树扫一遍，再扫一遍，扫到end的时候len(t)==1，说明不能压缩，如果len(t)>1，说明可以压缩。
解法2：先按长度排序，一边扫一边insert，如果startwith，不更新ans不insert，否则insert和更新ans。

from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
    def __init__(self):
        self.trie = TrieNode()
    def insert(self, word):
        reduce(dict.__getitem__, word, self.trie)['end'] = True
    def search(self, word):
        return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
    def startsWith(self, word):
        return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())
class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        tree=Trie()
        words =set(words)
        for word in words:
            tree.insert(word[::-1])
        ans=0
        for word in words:
            t=tree.trie
            for c in word[::-1]:
                t=t[c]
            if len(t)==1:
                ans+=len(word)+1
            else:
                continue
        return ans