Trie（發(fā)音類(lèi)似 "try"）或者說(shuō) 前綴樹(shù) 是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)食呻，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵亲轨。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景醇坝，例如自動(dòng)補(bǔ)完和拼寫(xiě)檢查扰柠。
請(qǐng)你實(shí)現(xiàn) Trie 類(lèi)：
Trie() 初始化前綴樹(shù)對(duì)象牡整。
void insert(String word) 向前綴樹(shù)中插入字符串 word 藐吮。
boolean search(String word) 如果字符串 word 在前綴樹(shù)中，返回 true（即，在檢索之前已經(jīng)插入）谣辞；否則迫摔，返回 false 。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix 泥从，返回 true 句占；否則，返回 false 歉闰。
示例：
輸入
inputs = ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
inputs = [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出
[null, null, true, false, true, null, true]
解釋
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 僅由小寫(xiě)英文字母組成
insert辖众、search 和 startsWith 調(diào)用次數(shù) 總計(jì) 不超過(guò) 3 * 104 次
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/QC3q1f
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)和敬，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處凹炸。
解題思路及方法
自己實(shí)現(xiàn)前綴樹(shù)，每一個(gè)節(jié)點(diǎn)通過(guò)一個(gè)長(zhǎng)度為26的Trie數(shù)組指向下一節(jié)點(diǎn)昼弟，通過(guò)字母序的順序來(lái)記錄字符串該節(jié)點(diǎn)字符啤它；同時(shí)isEnd表示某字符串是否在該節(jié)點(diǎn)結(jié)束。
插入操作：用一個(gè)Trie指針從根節(jié)點(diǎn)開(kāi)始舱痘，每一個(gè)節(jié)點(diǎn)按序記錄字符串的每一個(gè)字符变骡，如果該節(jié)點(diǎn)的該字符位為空，就新增子節(jié)點(diǎn)Trie芭逝，并移動(dòng)指針塌碌。遍歷到最后一位的時(shí)候?qū)⒃摴?jié)點(diǎn)的isEnd賦值true。
查找操作：用一個(gè)Trie指針從根節(jié)點(diǎn)開(kāi)始旬盯，遍歷字符串每一位字符并在節(jié)點(diǎn)的children數(shù)組尋找指定位是否為空台妆，為空表示不存在該字符，返回false胖翰；如果遍歷到最后一位字符都不為空接剩，就判斷該節(jié)點(diǎn)的isEnd是否為true。
startsWith操作：遍歷到最后一位時(shí)補(bǔ)不需要判斷isEnd是否為空萨咳，只需在遍歷的過(guò)程中判斷每一位字符節(jié)點(diǎn)是否為空懊缺。
class Trie {
private Trie[] children;
private boolean isEnd;
/** Initialize your data structure here. */
public Trie() {
this.children = new Trie[26];
this.isEnd = false;
}
/** Inserts a word into the trie. */
public void insert(String word) {
// 前綴樹(shù)節(jié)點(diǎn)指針
Trie nodePt = this;
// 遍歷字符串構(gòu)建前綴樹(shù)
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (nodePt.children[idx] == null) {
nodePt.children[idx] = new Trie();
}
// 移動(dòng)指針
nodePt = nodePt.children[idx];
}
nodePt.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
// 前綴樹(shù)結(jié)點(diǎn)指針
Trie pt = this;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (pt.children[idx] == null) return false;
// 移動(dòng)指針
pt = pt.children[idx];
}
return pt.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
// 前綴樹(shù)結(jié)點(diǎn)指針
Trie pt = this;
for (int i = 0; i < prefix.length(); i++) {
int idx = prefix.charAt(i) - 'a';
if (pt.children[idx] == null) return false;
// 移動(dòng)指針
pt = pt.children[idx];
}
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é)果如下：
