Trie Tree（一）（字典树）

Trie 树，字典树，try树。

• Trie 根节点不存在字符。
• 从根节点开始，每个节点都是一个字符，通过路径连接起来。

可以用数组，HashMap，和指针动态分配。
优势：时间复杂度低。插入和查询都是O(L)，L为字符串长度。

敲黑板！！！这里我跪过。

["world", "work", "see", "sold", "maven"] 的 Trie tree 表示如下：

trieTree.png

TrieNode定义(可根据情境更改定义)：

/**
 * TrieNode definition.
 */
class TrieNode {
    boolean isLeaf;
    Map<Character, TrieNode> children; // use Map.

    public TrieNode() {
        this.isLeaf = false;           // init false.
        children = new HashMap<>();    // don't forget it.
    }
}

/**
 * Another definition of Trie.
 */
class TrieNode {
    int count;
    char ch;
    TrieNode children;

    public TrieNode() {
        count = 1;
        children = new TrieNode[26];    // 插入和查找时间复杂度O(1)
    }
}

/**
 * Insert. 
 * Use definition one(containing Map).
 */
 public void insert(TrieNode node, String str) {
    if (str == null || str.length() == 0) {
        return;
    }
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (node.children.containsKey(ch)) {    // 如果查找到，则继续向下查找。
            node = node.children.get(ch);
        } else {                                // 未查找到，则生成新节点。
            TrieNode child = new TrieNode();
            node.children.put(ch, child);
        }
    }
    node.isLeaf = true;  // after for-loop, set leaf true.
 }

/**
 * Trie Tree
 * Search
 */
public boolean search(TrieNode node, String str) {
    if (str == null || str.isEmpty()) {
        return false;
    }
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (!node.children.containsKey(ch)) {
            return false;
        } else {
            node = node.children.get(ch);
        }
    }
    return node.isLeaf == true;
}

---

Trie树应用：
字符串最左前缀匹配；
word search.

例子：[LeetCode-212]. Word Search II

一个由小写字母组成的矩阵和一个字典，找出所有同时在字典和矩阵中出现的单词。
矩阵：
d o a f
a g a i
d c a n
字典：{"dog", "dad", "dgdg", "can", "again"}
返回结果：{"dog", "dad", "can", "again"}。

Word Search II 分析：

对字典建立Trie 树;
对矩阵每个元素进行遍历（2次for循环），然后DFS搜索。查找矩阵中是否存在字典中的字符串。
在DFS中，对于已经遍历过的字符，要进行标记。可以先存在temp变量中，然后标记为“*”，DFS返回的时候再取回temp中的值。

/**
 *  TrieNode
 */
class TrieNode {
    boolean isLeaf;
    Map<Character, TrieNode> children;

    public TrieNode() {
        isLeaf = false;
        children = new HashMap<>();
    }
}

/**
 *  TrieTree class.
 */
public class TrieTree {
    private TrieNode root;         // root node.

    public TrieTree() {
        root = new TrieNode();
    }

    public TrieNode getRoot() {    // return root node.
        return root;
    }
    
    // To insert a String list into Trie Tree.
    public void insertAll(List<String> list) {
        if (list == null || list.size() == 0) {
            return;
        }
        for (String str : list) {
            insertString(str);
        }
    }

    // To insert a String into Trie Tree.
    public void insertString(Stirng str) {
        if (str == null || str.isEmpty()) {
            return;
        }
        TrieNode node = root;    // to get reference of root.
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (!node.children.containsKey(ch)) {
                TrieNode child = new TrieNode();
                node.children.put(ch, child);
            }
            node = node.children.get(ch);  // if containing ch.
        }
        node.isLeaf = true;
    }

}

/**
 *  Search word, using DFS.
 */
public class WordSearch {
    
    public List<String> findWords(char[][] board, List<String> words) {
        if (words == null || words.size() == 0) {
            return new ArrayList<String>();
        }
        if (board.length == 0 || board[0].length == 0) {
            return new ArrayList<String>();
        }
        Set<String> resSet = new HashSet<String>();
        TrieTree trieTree = new TrieTree();
        TrieNode root = trieTree.getRoot();
         
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {    // 两次for循环遍历二维数组。
            for (int j = 0; j < n; j++) {
                dfs(board, TrieNode root, resSet, "", i, j);    // DFS搜索
            }
        }
        return new ArrayList<String>(resSet);
    }

    /**
     * DFS
     */
    private void dfs(char[][] board, TrieNode root, Set<String> resSet, String word, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == '*') {
            return;
        }
        if (root.children.containsKey(board[i][j])) {
            word += board[i][j];
            root = root.children.get(board[i][j]);
            if (root.isLeaf) {    // 查找到叶子节点，添加结果
                resSet.add(word);
            }
            char tmp = board[i][j];
            board[i][j] = '*';    // 标记为已访问
            dfs(board, root, resSet, word, i + 1, j);
            dfs(board, root, resSet, word, i - 1, j);
            dfs(board, root, resSet, word, i, j + 1);
            dfs(board, root, resSet, word, i, j - 1);
            board[i][j] = tmp;    // 复原已访问中的元素
        }
        return;
    }

}

更多应用举例：Trie Tree(二)：Maximum XOR of Two Number in an Array?

[已完结]