LeetCode 筆記 - 208. Implement Trie (Prefix Tree)

就是實作 Trie 的基本功能，包含 insert, search, startsWith 三個方法。

解題思維

這題就是實作 Trie 的基本功能，這邊我們用一個 class TrieNone 來代表 Trie 的節點，然後再用 Trie 來實作 insert, search, startsWith 三個方法。

在這裡我們先來定義一個 TrieNone 的 class，這個 class 有兩個屬性，childs 代表子節點，is_end 代表是否為結尾。

class TrieNone:
    def __init__(self):
        self.childs = {}
        self.is_end = False

insert 就是按照資料建立節點，如果節點不存在就建立，最後一個節點的 is_end 設為 True。

search 就是從根節點開始，一個一個比對節點是否存在，如果不存在就回傳 False，如果最後一個節點的 is_end 為 True 就回傳 True。因為 search 需要完整的字串都存在，所以不用擔心前綴字串的問題。

startsWith 跟 search 很像，差異在於最後需不需要檢查 is_end，因為 startsWith 只需要前綴字串存在即可。

以下是插入 apple, app 之後資料結構的樣子：

我們可以觀察到，兩個有一樣的前綴 app，但是 apple 有 is_end，app 沒有，而且還共用了同樣的 prefix app。

程式碼

以下為完整程式碼：

class TrieNone:
    def __init__(self):
        self.childs = {}
        self.is_end = False

class Trie:

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

    def insert(self, word: str) -> None:

        node = self.root
        for w in word:
            if w not in node.childs:
                node.childs[w] = TrieNone()
            
            node = node.childs[w]

        node.is_end = True
        
    def search(self, word: str) -> bool:
        node = self.root

        for w in word:
            if w not in node.childs:
                return False
            
            node = node.childs[w]

        return node.is_end
        
    def startsWith(self, prefix: str) -> bool:

        node = self.root

        for w in prefix:
            if w not in node.childs:
                return False
            
            node = node.childs[w]

        return True

解題思維

程式碼

也許你也會想看看