數據結構-Trie 字典樹

        字典樹主要用於存儲字符串，查找速度主要字符串元素（單詞）的長度有關O(w)。字符串的推薦系統，可以通過字典樹來實現，也是一種深度優先搜索單詞的方法。利用字符串公共前綴來查詢單詞，進行搜尋引擎推薦。字典樹的查詢效率非常高，但是大量的數組並沒有元素，空間利用率低，是典型的空間換時間。

Trie中節點的定義：

    1. 單詞是否結束

    2. 前綴/單詞

    3. 記錄單詞數量

    4. 孩子節點，每個節點都有26個指向下個節點的指針，26個代表有26個字母的可能

/**
* 字典樹!!!======================================================!!!
*/
/**
* 字典樹節點
*/
private static class TrieNode {
//單詞是否結束
private boolean end;
//單詞
private String prefix;
//單詞可重複，數量
private int count;
//孩子節點
private TrieNode[] children = new TrieNode[26];
}

/**
* 字典樹
*/
private static class Trie {
//根節點
private TrieNode root = new TrieNode();
/**
* 插入單詞
*
* @param products
*/
private void insertWord(String[] products) {
for (String p : products) {
insertWord(p);
}
}

private void insertWord(String product) {
TrieNode node = root;
for (char c : product.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
if (!node.end) {
node.end = true;
node.prefix = product;
}
node.count++;
}

/**
* 查詢單詞
*
* @param searchWord
* @return
*/
private List<List<String>> searchWord(String searchWord) {
List<List<String>> result = new ArrayList<>(searchWord.length());
for (int i = 0; i < searchWord.length(); i++) {
result.add(searchPrefix(searchWord.substring(0, i + 1)));
}
return result;
}

/**
* 查詢單詞前綴
*
* @param pattern
* @return
*/
private List<String> searchPrefix(String pattern) {
List<String> temp = new ArrayList<>();
TrieNode node = root;
for (char c : pattern.toCharArray()) {
if (node.children[c - 'a'] == null) {
return temp;
}
node = node.children[c - 'a'];
}
suggest(node, temp);
return temp;
}

/**
* 遞歸深度優先搜索單詞
*
* @param node
* @param temp
*/
private void suggest(TrieNode node, List<String> temp) {
if (node.end) {
for (int i = 0; i < node.count; i++) {
temp.add(node.prefix);
if (temp.size() == 3) {
return;
}
}
}
for (TrieNode t : node.children) {
if (t != null) {
suggest(t, temp);
}
//注意這裡也需要添加==3的判斷，否則會繼續遞歸，導致size>3
if (temp.size() == 3) {
return;
}
}
}
}