a 字典树

1 trie树

又称单词查找树或键树，是哈希树的变种。典型应用是用于统计和排序大量的字符串，经常被搜索引擎系统用于文本词频统计。
优点：最大限度的减少无畏的字符串比较，查询效率比哈希表高。
思想：空间换时间
性质：根节点不包含字符，除根节点外每一个节点都只包含一个字符

实际问题（如搜索）：
搜索 bit
返回 bitcoin
     bitfinex icon
     bitcoin price等

python：
class TrieNode:
    # Trie node class
    def __init__(self):
        self.children = [Node] * ALPHABET_SIZE
        self.isEndOfWord = False

2 实现Trie (leetcode 208)

class Trie:
    def __init__(self):
        self.root = {}
        self.end_of_word = '#'
    
    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

3 二维网格中的单词搜索问题 (leetcode 212)

输入：
words = ['oath','pea','eat','rain']
board = [
         ['o','a','a','n'],
         ['e','t','a','e'],
         ['i','h','k','r'],
         ['i','f','l','v']
          ]
输出：['eat', 'oath']

#method1 DFS

#method2 Trie
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

END_OF_WORD = '#'

class Solution:
    def findWords(self, board, words):
        if not board or not board[0]: return []
        if not words: return []

        self.result = set()
        root = collections.defaultdict()
        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char, collections.defaultdict())
            node[END_OF_WORD] = END_OF_WORD

        self.m, self.n = len(board), len(board[0])
        
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] in root:
                    self._dfs(board, i, j, '', root)

    def _dfs(self, board, i, j, cur_word, cur_dict):
        cur_word += board[i][j]
        cur_dict = cur_dict[board[i][j]]
        if END_OF_WORD in cur_dict:
            self.result.add(cur_word)
        tmp, board[i][j] = board[i][j], '@'
        for k in range(4):
            x, y = i + dx[k], j + dy[k]
            if 0 <= x < self.m and 0 <= y < self.n and board[x][y] != '@' and board[x][y] != '@' and board[x][y] in cur_dict:
                self._dfs(board, x, y, cur_word, cur_dict)
        board[i][j] = tmp