每日一題 | Python3 實現(xiàn)「208. 實現(xiàn) Trie(前綴樹)」
208. 實現(xiàn) Trie (前綴樹)
題目鏈接
https://leetcode-cn.com/problems/implement-trie-prefix-tree/
也可以點擊「閱讀原文」直達題目鏈接。
題目描述
Trie（發(fā)音類似 "try"）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)，用于高效地存儲和檢索字符串數(shù)據(jù)集中的鍵。這一數(shù)據(jù)結(jié)構(gòu)有相當多的應用情景，例如自動補完和拼寫檢查。
請你實現(xiàn) Trie 類：
Trie()初始化前綴樹對象。void insert(String word)向前綴樹中插入字符串word。boolean search(String word)如果字符串word在前綴樹中，返回true（即，在檢索之前已經(jīng)插入）；否則，返回false。boolean startsWith(String prefix)如果之前已經(jīng)插入的字符串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 <= 2000word和prefix僅由小寫英文字母組成insert、search和startsWith調(diào)用次數(shù) 總計 不超過 次
解題思路
這道題考查的是前綴樹的思想。
前綴樹在實際的工程應用中有著很大的應用。很常見的包括搜索引擎的關(guān)鍵詞提示功能，以及 IDE 的自動補全功能等等...
Trie 樹的本質(zhì)是將重復的前綴子串進行合并的思想，也就是說如果一個字符出現(xiàn)了多次，但是只需要存儲一次就可以了。
剛開始的時候，Trie 樹是一顆空樹，Trie 樹的構(gòu)造過程就是相當于往 Trie 樹中插入字符串，當字符串插入完畢后，Trie 樹就構(gòu)造完成了。
這里我找了一個 Trie 構(gòu)造過程，你可以看下。假定要插入的字符串一共有 6 個，分別是"how", "hi", "her", "hello", "so", "see"。紅色節(jié)點表示一個字符串的結(jié)尾。
那么應該如何實現(xiàn)呢？因為題目中我們假定字符串只包含小寫字母。因為小寫字母一共有 26 個，仿照二叉樹的存儲方式，我們可以使用一個大小為 26 的數(shù)組來存儲其孩子節(jié)點。另外，對于每一個節(jié)點，還需要一個額外的變量來記錄此節(jié)點代表的字符是否是一個字符串的結(jié)尾，為 True 的話代表著圖中的紅色節(jié)點。
另外呢，因為數(shù)組有天然的支持下標索引的特性，因此我們甚至可以不存儲節(jié)點存儲的數(shù)據(jù)，因為在進行查找的時候，直接通過字符 ASCII 碼的相對值作為訪問孩子數(shù)組的下標即可。
Python3 代碼
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self._children = [None] * 26
self._is_ending_char = False
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
root = self
for index, char in map(lambda x: (ord(x) - ord("a"), x), word):
if not root._children[index]:
root._children[index] = Trie()
root = root._children[index]
root._is_ending_char = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
root = self
for index in map(lambda x: ord(x) - ord("a"), word):
if not root._children[index]:
return False
root = root._children[index]
return root._is_ending_char
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
root = self
for index in map(lambda x: ord(x) - ord("a"), prefix):
if not root._children[index]:
return False
root = root._children[index]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
復雜度分析：
時間復雜度：
空間復雜度：
其中 n 為要插入字符串的總長度，k 為查詢字符串的長度。也就是說，Trie 樹構(gòu)造完成后，查詢的時間復雜度只和要查詢字符串的長度有關(guān)，而構(gòu)造 Trie 樹，也就是插入的時候，時間復雜度是所有要插入的字符串的長度之和。
總結(jié)
雖然 Trie 樹的思想是合并重復的前綴子串，看上去節(jié)省了存儲空間，但實際上 Trie 樹利用的是空間換時間的思想，因為每個節(jié)點需要一個孩子數(shù)組，用于指向下一層的地址。在字符的范圍很大的時候，比如說不僅僅只有英文小寫字母的時候，光存儲 孩子數(shù)組就需要浪費很多的存儲空間。如果再考慮中文的話，所耗費的空間就更大了。
因此，Trie 樹有很多可以優(yōu)化的地方，比如說縮點優(yōu)化，感興趣的可以自己下去搜索下。還有一個常見的方法就是孩子數(shù)組利用有序數(shù)組來進行實現(xiàn)，不用事先申請全部字符所占的空間，遇到不存在的字符時，將其插入到其應該所在的位置即可。
好了，今天的內(nèi)容就到這里了。我最近在學習數(shù)據(jù)結(jié)構(gòu)與算法的相關(guān)知識，也會在力扣進行每日一題的打卡。如果你最近在求職面試或者也在進行力扣進行每日一題的打卡的話，歡迎加入我們，后臺回復「加群」即可。我一直堅信一個人走的更快，一群人走的更遠。很多時候，只要堅持下去了，那么你就超越了很多人。
參考資料：
https://time.geekbang.org/column/article/72414 https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/yu-ni-yi-qi-xue-suan-fa-python3-shi-xian-p0fr/