2024-02-27|閱讀時間 ‧ 約 0 分鐘

資料結構實作: Implement Trie 前綴樹Leetcode #208_精選75題

題目敘述

題目已經給定一個Trie前綴樹的類別和相關的函式介面interface,
要求我們把功能實作出來。

Trie() 建構子,初始化一個空的Trie。

void insert(String word)
插入一個新的單字word到Trie裡面。

boolean search(String word)
搜尋word是否存在Trie裡面,假如有,回傳True;如果沒有,回傳False。

boolean startsWith(String prefix)
搜尋prefix前綴是否存在Trie裡面,假如有,回傳True;如果沒有,回傳False。


題目的原文敘述


測試範例

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True

約束條件

Constraints:

  • 1 <= word.length, prefix.length <= 2000

單字的長度 和 前綴的長度都介於1~2000個字元之間。

  • word and prefix consist only of lowercase English letters.

輸入只會有英文小寫字母。

  • At most 3 * 10^4 calls in total will be made to insertsearch, and startsWith.

動態測試時,最多會有三萬次函式呼叫,包含insert(), search(), startWith()


演算法 多層架構 + 字典

其實Trie的結構和Tree很像,差別在於每一層儲存的是鍵值:字元,而映射到的value就是下一層的字典(Python dictionary)


1.建構子Trie()比較簡單,一開始初始化一個空的字典即可,代表初始化成空的Trie。

2.每當新插入一個單字insert(word)時,就依序把每一個字元從上到下,插入到Trie的多層架構字典中,最後再加上一個"@"當作結尾符號。

為什麼要有結尾符號?
是為了要區別search() 和 startWith()的對應結果。

search()比較嚴格,必須整個字串相同,才算有找到
startWith比較寬鬆,只要前綴prefix可以和Trie裡面的任何一個單字的前綴吻合,就算成功。

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.