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

Posted on

題目在此 208. Implement Trie (Prefix Tree)

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

解題思維

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

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

1
2
3
4
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。

程式碼

以下為完整程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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

也許你也會想看看