• 🙋?♂? 作者：海碼007
• 📜 專欄：算法專欄
• 💥 標題：【Hot 100】208. 實現 Trie (前綴樹)
• ?? 寄語：書到用時方恨少，事非經過不知難！

引言

實現 Trie (前綴樹)

• 🎈 題目鏈接：
• 🎈 做題狀態：

我的解題

首先需要理解前綴樹的定義，前綴樹是一顆多叉樹，樹根不存儲字母。每一層可能存儲26個不同的字母。然后每一個單詞對應這個多叉樹的一條路徑，并且路徑的結尾會標識是單詞的結尾。

class Trie {
private:bool isEnd;Trie* next[26]; //指針數組，有26個小寫字母public:Trie() {isEnd = false;memset(next, 0, sizeof(next));}// 插入一個單詞void insert(string word) {// node指向根節點并向下遍歷Trie* node = this;for (char c : word){// 判斷當前這個字母是否在當前層存在，如果不存在則創建一個新的樹。if (node->next[c-'a'] == nullptr){node->next[c-'a'] = new Trie();}node = node->next[c-'a'];   // 繼續往下遍歷}// 遍歷到末尾后，需要標識 endnode->isEnd = true;}// 搜索當前單詞是否存在，依次比較每個單詞是否存在每一層中bool search(string word) {Trie* node = this;for (const char& c : word){if (node->next[c-'a'] == nullptr){return false;}node = node->next[c-'a'];}return node->isEnd; // 遍歷到末尾后還需要判斷是否是單詞的結尾}// 判斷這個前綴樹是否包含 prefix 這個前綴bool startsWith(string prefix) {Trie* node = this;for (const char& c : prefix){if (node->next[c-'a'] == nullptr){return false;}node = node->next[c-'a'];}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);*/

代碼解析

該代碼實現了一個基本的前綴樹（Trie）結構，支持插入、搜索和前綴匹配功能。以下是對代碼的詳細分析和優化建議：

---

代碼思路分析

1. 數據結構設計：

   • isEnd：標記當前節點是否為單詞的結尾。
   • next[26]：一個包含 26 個指針的數組，對應英文小寫字母，用于構建字符到子節點的映射。

2. 核心方法：

   • 插入 (insert): 從根節點開始，逐字符向下遍歷。若字符對應的子節點不存在，則創建新節點。遍歷完成后，標記最后一個節點為單詞結尾。
   • 搜索 (search): 檢查單詞是否存在且最后一個節點被標記為結尾。
   • 前綴匹配 (startsWith): 僅檢查路徑是否存在，無需判斷結尾標記。

3. 正確性：

   • 邏輯正確，符合前綴樹的標準實現。
   • 使用 memset 初始化指針數組，確保初始值為 nullptr。

---

優化建議

1. 內存泄漏問題

當前代碼未釋放動態分配的子節點，導致內存泄漏。需添加析構函數遞歸釋放子節點：

~Trie() {for (int i = 0; i < 26; ++i) {delete next[i]; // 遞歸調用子節點的析構函數}
}

2. 使用智能指針優化內存管理

改用 std::unique_ptr 管理子節點，避免手動釋放內存：

class Trie {
private:bool isEnd;std::array<std::unique_ptr<Trie>, 26> next; // 使用智能指針public:Trie() : isEnd(false) {} // 無需 memsetvoid insert(string word) {Trie* node = this;for (char c : word) {if (!node->next[c - 'a']) {node->next[c - 'a'] = std::make_unique<Trie>();}node = node->next[c - 'a'].get();}node->isEnd = true;}// search 和 startsWith 無需修改
};

3. 輸入合法性校驗（可選）

若需處理非法字符（如大寫字母），可在插入/查詢前添加校驗：

void insert(string word) {for (char c : word) {if (c < 'a' || c > 'z') {throw std::invalid_argument("Invalid character");}}// 原插入邏輯
}

4. 其他優化

• 空間優化：使用壓縮 Trie 樹（如 Ternary Search Tree）減少內存占用，但會增加實現復雜度。
• 性能優化：當前時間復雜度為 O(L)（L 為字符串長度），已是最優，無需調整。

---

總結

代碼邏輯正確，但存在內存泄漏問題。建議通過析構函數或智能指針優化內存管理。其他優化可根據實際需求選擇。改進后的代碼示例（使用智能指針）如下：

#include <memory>   // 用于智能指針 unique_ptr
#include <array>    // 用于固定大小的數組 array
#include <string>   // 用于字符串操作class Trie {
private:// 標記當前節點是否為某個單詞的結尾bool isEnd;// 使用智能指針管理子節點，避免內存泄漏// 數組大小為26，對應英文小寫字母a-zstd::array<std::unique_ptr<Trie>, 26> next;public:// 構造函數：初始化 isEnd 為 false，表示初始時不是單詞結尾// 智能指針數組 next 會自動初始化為 nullptrTrie() : isEnd(false) { }/*** 插入一個單詞到 Trie 樹中* @param word 待插入的單詞*/void insert(const std::string& word) {// 從根節點（this）開始遍歷Trie* node = this;// 逐個字符處理for (char c : word) {// 計算字符對應的索引（a->0, b->1, ..., z->25）int idx = c - 'a';// 如果當前字符的子節點不存在，則創建新節點if (node->next[idx] == nullptr) {node->next[idx] = std::make_unique<Trie>();}// 移動到子節點繼續處理node = node->next[idx].get();  // get() 獲取裸指針}// 標記單詞的最后一個字符節點為結尾node->isEnd = true;}/*** 搜索 Trie 樹中是否存在某個單詞* @param word 待搜索的單詞* @return 如果單詞存在且完整匹配（最后一個字符是結尾），返回 true；否則返回 false*/bool search(const std::string& word) {// 從根節點開始遍歷Trie* node = this;// 逐個字符檢查for (const char& c : word) {int idx = c - 'a';// 如果當前字符的子節點不存在，說明單詞不存在if (node->next[idx] == nullptr) {return false;}// 移動到子節點繼續檢查node = node->next[idx].get();}// 檢查最后一個字符是否被標記為單詞結尾return node->isEnd;}/*** 檢查 Trie 樹中是否存在某個前綴* @param prefix 待檢查的前綴* @return 如果前綴存在（不要求是完整單詞），返回 true；否則返回 false*/bool startsWith(const std::string& prefix) {// 從根節點開始遍歷Trie* node = this;// 逐個字符檢查for (const char& c : prefix) {int idx = c - 'a';// 如果當前字符的子節點不存在，說明前綴不存在if (node->next[idx] == nullptr) {return false;}// 移動到子節點繼續檢查node = node->next[idx].get();}// 只要路徑存在，無論是否是單詞結尾，都返回 truereturn true;}
};