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?
[已完结]
