分類

展開全部 | 收合全部

分類

展開全部 | 收合全部

【Leetcode】python – [208] Implement Trie (Prefix Tree) 個人解法筆記

題目出處

208. Implement Trie (Prefix Tree)

難度

medium

個人範例程式碼

class TrieNode:
    def __init__(self):
        self.children = {}
        self.hasword = False # only True if exist word, 
        # apple in dict, but app not in, False

class Trie:

    def __init__(self):
        self.root = TrieNode()        

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]                
        cur.hasword = True

    def search(self, word: str) -> bool:
        cur  = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.hasword


    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        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)

算法說明

資料結構設計類型的題目,考的就是設計資料結構的能力,比較難。
這邊要實作的有三個功能,startsWith, search, insert,

我們先來了解 Trie (字典樹)

Trie (字典樹) 是用來特化搜尋「前綴文字 Prefix」用的資料結構,
特色就是我們把每個單字建成一個樹狀,而當我們搜尋一個前綴字時,能夠快速順著字典往下,

一個 TrieNode 會有,

  • childrens:紀錄往下的字母
  • hasword:到此本身是否有這個文字

    特別注意 hasword 的功能,例如 apple 在字典中,
    但沿著路徑我們會搜尋到 app,為了反映 app 這個字不屬於字典的字,
    我們用 hasword 來記錄這個點。(apple 紀錄在 e 上,app 如果有,會記錄在最後一個 p 上。)

    Trie (字典樹) 範例圖

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

input handling

x

Boundary conditions

注意搜尋的過程中,有時候可以有搜尋到路徑,但實際上沒有那個文字,所以我們會需要 hasword 這個 bool,
例如我們有 apple 在 Trie 中,
沿路會看到 app,但不表示搜尋到 app 就有 app 這個字。

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!
另外,因為定位是「個人的隨手筆記」,有些文章內容「⚠️可能我理解有誤⚠️」或「?只寫到一半?」,如果有發現這樣的情況,歡迎在該文章的最下面留言提醒我!我會儘快修正或補上!感謝大家的建議與幫忙,讓網站能變得更好?

文章: 866

★留個言吧!內容有誤或想要補充也歡迎與我討論!