Trie 樹，字典樹拇囊，try樹迂曲。
- Trie 根節(jié)點(diǎn)不存在字符。
- 從根節(jié)點(diǎn)開始寂拆，每個節(jié)點(diǎn)都是一個字符奢米，通過路徑連接起來。
可以用數(shù)組纠永，HashMap，和指針動態(tài)分配谒拴。
優(yōu)勢：時間復(fù)雜度低尝江。插入和查詢都是O(L)，L為字符串長度英上。敲黑板Ｌ啃颉！苍日！這里我跪過惭聂。
["world", "work", "see", "sold", "maven"] 的 Trie tree 表示如下：
trieTree.png
TrieNode定義(可根據(jù)情境更改定義)：
/**
* 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]; // 插入和查找時間復(fù)雜度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)) { // 如果查找到，則繼續(xù)向下查找相恃。
node = node.children.get(ch);
} else { // 未查找到辜纲，則生成新節(jié)點(diǎn)。
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樹應(yīng)用：
字符串最左前綴匹配；
word search.
例子：[LeetCode-212]. Word Search II
一個由小寫字母組成的矩陣和一個字典耕腾，找出所有同時在字典和矩陣中出現(xiàn)的單詞见剩。
矩陣：
d o a f
a g a i
d c a n
字典：{"dog", "dad", "dgdg", "can", "again"}
返回結(jié)果：{"dog", "dad", "can", "again"}。
Word Search II 分析：
對字典建立Trie 樹;
對矩陣每個元素進(jìn)行遍歷（2次for循環(huán)）扫俺，然后DFS搜索苍苞。查找矩陣中是否存在字典中的字符串。
在DFS中狼纬，對于已經(jīng)遍歷過的字符羹呵，要進(jìn)行標(biāo)記×屏穑可以先存在temp變量中冈欢，然后標(biāo)記為“*”，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循環(huán)遍歷二維數(shù)組涛癌。
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) { // 查找到葉子節(jié)點(diǎn)，添加結(jié)果
resSet.add(word);
}
char tmp = board[i][j];
board[i][j] = '*'; // 標(biāo)記為已訪問
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; // 復(fù)原已訪問中的元素
}
return;
}
}
更多應(yīng)用舉例：Trie Tree(二)：Maximum XOR of Two Number in an Array?
[已完結(jié)]
