算法：Trie字典树

• 字典树及经典题目
• • 一、字典树Trie
  • 二、经典题目
  • • 2.1 [208. 实现 Trie (前缀树)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/)
    • 2.2 [212. 单词搜索 II](https://leetcode-cn.com/problems/word-search-ii/)
    • 2.3 [79. 单词搜索](https://leetcode-cn.com/problems/word-search/) , DFS

（空间换时间）

• 优点：最大限度的减少无谓的字符串比较，查询效率比哈希表高；
• 使用场景：统计和排序大量的字符串。经常被搜索引擎用于文本词频统计；
• 特性：
  • 节点不存完整单词；
  • 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串；
  • 不同路径代表的字符串都不相同；
  • 节点上添加数值，可以代表统计频次，对用户进行推荐；

Java实现：

class Trie {

    private Trie[] t;
    private static final int R = 26;
    private boolean end;
    public Trie() {
        t = new Trie[R];
    }
    public void insert(String word) {
        Trie x = this;
        for (int i=0; i 
python的实现
 
class Trie:

    def __init__(self):
        self.root = {}
        self.end_of_word = '#'


    def insert(self, word: str) -> None:
        m = self.root
        for w in word:
            m = m.setdefault(w, {})
        m[self.end_of_word] = {}


    def search(self, word: str) -> bool:
        m = self.root
        for w in word:
            if w in m:
                m = m[w]
            else:
                return False
        return self.end_of_word in m


    def startsWith(self, prefix: str) -> bool:
        m = self.root
        for w in prefix:
            if w in m:
                m = m[w]
            else:
                return False
        return True
 
2.2 212. 单词搜索 II 
private int[] dx = {1, -1, 0, 0};
    private int[] dy = {0, 0, 1, -1};
    public List findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word: words) {
            trie.insert(word);
        }

        Set resList = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        for (int i=0; i(resList);
    }

    private void dfs(char[][] board, int i, int j, Trie trie, StringBuilder sb, Set resList) {
        if (!trie.findPrefix(sb.toString())) {
            return;
        }
        if (trie.findWord(sb.toString())) {
            resList.add(sb.toString());
        }
        for (int k=0; k=board.length || y<0 || y>=board[0].length || board[x][y]=='#') {
                continue;
            }
            sb.append(board[x][y]);
            char c = board[x][y];
            board[x][y] = '#';
            dfs(board, x, y, trie, sb, resList);
            sb.deleteCharAt(sb.length()-1);
            board[x][y] = c;
        }

    }

    private class Trie{
        private Trie[] tries;
        private static final int R = 26;
        private boolean end;
        public Trie() {
            tries = new Trie[R];
        }

        public void insert(String word) {
            Trie x = this;
            for (int i=0; i 
2.3 79. 单词搜索 , DFS 
    private int[] dx = {0, 0, 1, -1};
    private int[] dy = {1, -1, 0, 0};
    public boolean exist(char[][] board, String word) {
        // https://leetcode-cn.com/problems/word-search/
        StringBuilder sb = new StringBuilder();
        for (int i=0; i=board.length || y<0 || y>=board[0].length || board[x][y]=='#') {
                continue;
            }
            sb.append(board[x][y]);
            char c = board[x][y];
            board[x][y] = '#';
            boolean res = dfs(x, y, board, sb, word);
            board[x][y] = c;
            sb.deleteCharAt(sb.length()-1);
            if (res) {
                return res;
            }
        }
        return false;
    }