一、題目大意
Trie（發音類似 "try"）或者說 前綴樹 是一種樹形資料結構，用于高效地存盤和檢索字串資料集中的鍵，這一資料結構有相當多的應用情景，例如自動補完和拼寫檢查，
請你實作 Trie 類：
-
Trie() 初始化前綴樹物件，
-
void insert(String word) 向前綴樹中插入字串 word ，
-
boolean search(String word) 如果字串 word 在前綴樹中，回傳 true（即，在檢索之前已經插入）；否則，回傳 false ，
-
boolean startsWith(String prefix) 如果之前已經插入的字串 word 的前綴之一為 prefix ，回傳 true ；否則，回傳 false ，
示例：
輸入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["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 僅由小寫英文字母組成
- insert、search 和 startsWith 呼叫次數 總計 不超過 3 * 104 次
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/implement-trie-prefix-tree
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
這道題讓我們實作一個資料結構-字典樹，又稱前綴樹或單詞查找樹，
字典樹主要有如下三個性質：
1、根節點不包含字符，除根節點外每個節點只包含一個字符
2、從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字串
3、每個節點的所有子節點包含的字串不相同
字典樹的插入、洗掉和查找都不難，用一個一重回圈即可，即第i次回圈找到前i個字母所對應的子樹，然后進行相應的操作，實作這棵字母 樹，可以用最常見的陣列保存即可（靜態開辟記憶體），至于節點對兒子的指向，一般有三種方法：
1、對每個節點開一個字母集大小的陣列，對應的下標是兒子所表示的字母，內容則是這個兒子對應在大陣列上的位置，即標號
2、對每個節點掛一個鏈表，按一定順序記錄每個兒子是誰
3、使用左兒子右兄弟表示法記錄這棵樹
第一種：易實作但實際空間要求較大
第二種：易實作空間要求較小但比較費時
第三種：空間要求最小但相對費時且不易寫
我們用第一種方法實作，字典樹的每個節點要定義一個大小為26位元組的int陣列，然后用一個標志符來記錄到當前位置為止是否為一個詞，初始化的時候將26個節點都賦為空，那么insert操作只需要對要插入的字串的每個字符計算出其位置，然后找是否存在在這個節點，若不存在則新建一個，然后再查找下一個，查找詞和找前綴操作跟insert操作很類似，不同點在于若不存在子節點則回傳false，查找到最后還要看標識位，而找前綴直接回傳true即可，
三、解題方法
3.1 Java實作
class TrieNode {
TrieNode[] child;
boolean isWord;
TrieNode() {
this.isWord = false;
child = new TrieNode[26];
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.child[i] == null) {
p.child[i] = new TrieNode();
}
p = p.child[i];
}
p.isWord = true;
}
public boolean search(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.child[i] == null) {
return false;
}
p = p.child[i];
}
return p.isWord;
}
public boolean startsWith(String prefix) {
TrieNode p = root;
for (char c : prefix.toCharArray()) {
int i = c - 'a';
if (p.child[i] == null) {
return false;
}
p = p.child[i];
}
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);
*/
四、總結小記
- 2022/9/26 養成一個小習慣然后堅持下來
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509615.html
標籤：其他
上一篇：一、目標檢測概述