Trie樹了袁，即字典樹朗恳、前綴樹，又稱單詞查找樹或鍵樹载绿，是一種樹形結(jié)構(gòu)粥诫，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串）崭庸，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計怀浆。它的優(yōu)點是：最大限度地減少無謂的字符串比較。
總的來說怕享，Trie的思想是以空間換空間执赡，利用字符串的公共前綴來降低查找操作帶來的時間開銷以達到提高效率的目的。
主要性質(zhì)：
- 根節(jié)點不包含字符函筋，除根節(jié)點之外每一個節(jié)點都只包含有且一個字符沙合；
- 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來跌帐，為該節(jié)點對應(yīng)的字符串首懈；
- 每個節(jié)點的所有子節(jié)點包含的字符都不相同；
一.字典樹的定義
public class Trie{
Trie[] root; //孩子節(jié)點谨敛，代表下一個字符
boolean isPause; //是否終止
public Trie(){
root = new Trie[26];
isPause = false;
}
}
二.字典樹的創(chuàng)建
void insert(String word)向前綴樹中插入字符串 word 究履。
栗子：好比假設(shè)有b，abc脸狸，abd最仑，bcd，abcd肥惭，efg盯仪，hii 這6個單詞,那我們創(chuàng)建trie樹就得到：
img
所以我們可以得到以下代碼：
/** Inserts a word into the trie. */
public void insert(String word) {
int length = word.length();
Trie cur = this;
for(int i = 0; i < length; i++){
int index =word.charAt(i) - 'a'; //這里獲得第i個字符的所在位置
if(cur.children[index] == null){//如果該分支不存在，那么創(chuàng)建
cur.children[index] = new Trie();
}
cur = cur.children[index]; //令cur指向當前單詞蜜葱，準備執(zhí)行下一次操作
}
//單詞插入完成后全景，需要將其此單詞末尾字符的標記位 置true,代表此字符是單詞的結(jié)尾
cur.isPause = true;
}
三.字符串的查找
/** Returns if the word is in the trie. */
public boolean search(String word) {
int length = word.length();
Trie cur = this;
for(int i = 0; i < length; i++){
int index = word.charAt(i) - 'a';
//如果下一個字符匹配不上，直接返回牵囤。
if(cur.children[index] == null){
return false;
}else{
cur = cur.children[index];
}
}
//遍歷所有待查詢單詞的字符爸黄，返回待查詢末尾字符是否為一個單詞的結(jié)尾字符。
return cur.isPause;
}
四.字符串前綴的查找
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix 揭鳞，返回 true 炕贵；否則，返回 false 野崇。
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
int length = prefix.length();
Trie cur = this;
for(int i = 0; i < length; i++){
int index = prefix.charAt(i) - 'a';
//如果下一個字符匹配不上称开，直接返回。
if(cur.children[index] == null){
return false;
}else{
cur = cur.children[index];
}
}
//這里和字符串查詢的區(qū)別在于， 只要滿足一個單詞的前綴就返回true
return true;
}
五.代碼匯總
class Trie {
Trie[] children;
boolean isPause;
/** Initialize your data structure here. */
public Trie() {
children = new Trie[26];
isPause = false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
int length = word.length();
Trie cur = this;
for(int i = 0; i < length; i++){
int index =word.charAt(i) - 'a';
if(cur.children[index] == null){
cur.children[index] = new Trie();
}
cur = cur.children[index];
}
cur.isPause = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
int length = word.length();
Trie cur = this;
for(int i = 0; i < length; i++){
int index = word.charAt(i) - 'a';
if(cur.children[index] == null){
return false;
}else{
cur = cur.children[index];
}
}
return cur.isPause;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
int length = prefix.length();
Trie cur = this;
for(int i = 0; i < length; i++){
int index = prefix.charAt(i) - 'a';
if(cur.children[index] == null){
return false;
}else{
cur = cur.children[index];
}
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
總結(jié)
時間復(fù)雜度：初始化為 O(1)鳖轰，其余操作為 O(|S|)清酥，其中 |S| 是每次插入或查詢的字符串的長度。
