# 前綴樹 (Prefix Trie)

## 用途

前綴樹是一個對字串搜索和比對非常高效的資料結構，常用在於 Auto complete、Spell checker 等應用上

## 結構

前綴樹通常使用 Linked List + HashMap 的組合，其中 Linked List 適用於連接字串的每一個字母，而每個 Linked List 中會有一個 HashMap，用於儲存下一個字串的指針，另外還會有一個布林值紀錄是否到達字串的尾端

class TrieNode:
    def __init__(self):
        self.end = False
        self.map = {}


## 方法

前綴樹的操作方法有以下：

1. insert(word: str) -> 插入新的字串
2. search(word: str) -> 搜索字串
3. startWith(prefix: str) -> 搜索字串前綴

## 複雜度

### Time complexity:

1. insert(word: str) -> O(s)
2. search(word: str) -> O(s)
3. startWith(word: str) -> O(s)

**s 代表輸入字串總長度**

### Space complexity: O(|s|)

**|s| 代表不重複字符集的總和**

## 實作

class TrieNode:
    def __init__(self):
        self.end = False
        self.map = {}

class Trie:

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

    def insert(self, word: str) -> None:
        cur = self.head
        for c in word:
            if c not in cur.map:
                cur.map[c] = TrieNode()
            cur = cur.map[c]
        cur.end = True # 使用 end 紀錄字串最後位置

    def search(self, word: str) -> bool:
        cur = self.head
        for c in word:
            if c not in cur.map:
                return False
            cur = cur.map[c]
        return cur.end # 查看是否為字串最後的位置

    def startsWith(self, prefix: str) -> bool:
        cur = self.head
        for c in prefix:
            if c not in cur.map:
                return False
            cur = cur.map[c]
        return True # 因為是看 prefix 不需要字串真的有插入過 直接返回 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)

## 參考資料

<iframe width="560" height="315" src="https://www.youtube.com/embed/oobqoCJlHA0?si=777mCghXNGPVMm7e" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>