# **程式筆記(Trie)**

:::info
:information_source: 日期 : 2023/07/07
:::

**:thumbsup:** Trie基本操作

* Trie起手式

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

* 樹根(會在起始字母的上一行)

self.root = TrieNode()

* tail.children[c]

tail.children[c]本身是一個TrieNode()
假設c是字母
tail.children[c] = TrieNode()

tail.children擁有一個字典，這個字典的key是字母c，value是一個TrieNode()

以下寫法，就是取出dict的key和value，分別會是字母和TrieNode()

for key, child in tail.children.items():

* 如何跳到下一個字母?

tail = tail.children[c]

* 基本操作

* 優點
Trie很常用於字典，因為省記憶體

                                    ◎
                                   / \
                                  a   b
                                 /     \
                                n       e 
                               / \       \
                              d   t       a (3)
                             (0)  (1)      \
                                            r (2)

**:thumbsup:**

Implement Trie (Prefix Tree) 經典範例

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

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.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.end = True

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

    def startsWith(self, prefix: str) -> bool:
        cur = self.head
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

* Design Add and Search Words Data Structure
需要如果遇到"."，則對它同等級的字母進行dfs

# dfs 錯誤寫法

1. 不能用enumerate，因為enumerate的index是從0開始
2. 不能用i 因為每次i都會是0 (目前還不懂)
for c in word[i:]
    if c == ".":
        for key, val in cur.children.items():
            if self.find(cur.children[key], word, i + 1):
                return True

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

class WordDictionary:

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

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

    def search(self, word: str) -> bool:
        cur = self.head
        return self.find(cur, word, 0)    

    def find(self, cur, word, i):
        for j in range(i, len(word)):
            c = word[j]
            if c == ".":
                for key, val in cur.children.items():
                    if self.find(cur.children[key], word, j + 1):
                        return True
                return False
            else:
                if c in cur.children:
                    cur = cur.children[c]
                else:
                    return False
        # 達成條件是要剛好遍歷完word 也剛好在樹的最尾巴
        return cur.end

**講解連結**
https://hackmd.io/@sysprog/BkE3uSvdN
Provided by. me & @sysprog

###### tags: `trie` `note` `code`