208. 實現 Trie (前綴樹) - 力扣（LeetCode）

題目

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?次

思路（以下思路是經過檢索學習后得出，有一部分的構造方法超出我的知識面了，所以不看的話構造不出來）

1. 首先這個類本身并沒有內置于C++中，需要自己構造。
2. 這個樹的思路比較清楚，是個26叉樹，因為其子節點分別都有可能是26個字母（除非存在某個字母不是英文單詞的開頭，不過顯然應該不存在這種情況），然后它還要具有一個功能就是判斷到達該節點時是不是組成了一個單詞。
3. 有了這兩個基本的點那么就需要構造前綴樹的節點類：
   1. 定義一個bool類型變量作為是否是一個單詞的判斷，再每次插入完成后，對最后一個節點標記為單詞位。
   2. 另外需要保存子節點的指針，這里我以為可以直接繼續創建對象數組，但是查了一下發現C++僅支持定義自身類型的靜態對象或者是對象的指針，所以其實還是對樹節點的構造方式不夠了解——那么就是構造一個TrieNode* children[26]即可。
   3. 以上都需聲明為public類型，否則默認是private的，這樣其他類就無法調用。
4. 接下來是操作邏輯：
   1. 初始化：現在Trie類中定義一個root的TrieNode*節點作為初始節點。
   2. 插入(insert)：從根節點和插入單詞頭開始順序檢查對應位置的單詞是否在鏈中，若在就往下搜，若不在就對該子節點創建一個新的TrieNode對象。不斷重復知道單詞遍歷完成，最后將當前達到的節點的isWord更新為true。
   3. 查找(search)：從根節點開始出發，根據待查找單詞從頭到尾的順序順鏈查找是否已經創建了對應的子節點對象，若是空指針，直接返回false。若遍歷完整個單詞了，需檢查對應的到達節點的isWord是否為true。
   4. 查找前綴(startsWith)：和search的方法類似，但最后一步不需要判斷isWord，只要能找到這，那么就一定是前綴，直接返回true即可。

代碼實現

class TrieNode {public:bool isWord = false;TrieNode* children[26];
};
class Trie {
public:TrieNode* root;Trie() {root = new TrieNode();}void insert(string word) {TrieNode* cur = root;char c;for(int i = 0; i < word.length(); ++i) {c = int(word[i]-'a');if(cur->children[c] == nullptr) cur->children[c] = new TrieNode();cur = cur->children[c];}cur->isWord = true;}bool search(string word) {TrieNode* cur = root;char c;for(int i = 0; i < word.length(); ++i) {c = int(word[i]-'a');if(cur->children[c] == nullptr) return false;cur = cur->children[c];}return cur->isWord;}bool startsWith(string prefix) {TrieNode* cur = root;char c;for(int i = 0; i < prefix.length(); ++i) {c = int(prefix[i]-'a');if(cur->children[c] == nullptr) return false;cur = cur->children[c];}return true;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

復雜度分析

• 時間復雜度：因為直接順鏈查找即可，插入、查找、判斷前綴的時間復雜度都是O(n)的，初始化的時間復雜度是O(1)的。
• 空間復雜度：設需要插入的字符串長度之和為L，那么最壞情況的空間復雜度就是26L，若擴展應用范圍，如果不是26個字符，而是字符集規模為S，則空間復雜度為O(LS)。

題解

• 官解的節點的實現是內置的，將Trie類直接當成TrieNode使用，邏輯也是一致的，不過感覺這樣寫對于類的定義就很模糊，感覺有點dirty，樹和節點還是分開定義比較好，不然屬性展現的是節點的屬性，函數卻展現的是樹的功能。——雖然代碼量少了，但是可讀性就差了，感覺不是個好實現。
• 官解有一個點很可取，判斷前綴和查找的功能有很大程度的重合，是可以封裝的，確實得鍛煉鍛煉對這種情況的直覺，避免寫出太冗余的代碼。
• 看了其他人的題解發現自己還是太死板了，直接用哈希表貌似很快就能秒了。
  • 首先存一個單詞哈希表，然后每次插入定義一個循環存前綴哈希表，時間復雜度是一致的。但是空間復雜度小了，因為很多沒出現的節點就不用另外保存了！
  • 還是聰明人多啊！