---
# System prepended metadata

title: '**程式筆記(Trie)**'
tags: [trie, code, note]

---

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


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


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

* Trie起手式
```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False
```

* 樹根(會在起始字母的上一行)
```python
self.root = TrieNode()
```

* tail.children[c]
```python
tail.children[c]本身是一個TrieNode()
假設c是字母
tail.children[c] = TrieNode()
```
tail.children擁有一個字典，這個字典的key是字母c，value是一個TrieNode()

以下寫法，就是取出dict的key和value，分別會是字母和TrieNode()
```python
for key, child in tail.children.items():
```

* 如何跳到下一個字母?
```python
tail = tail.children[c]
```

* 基本操作
![](https://hackmd.io/_uploads/HJeidp21a.png)


* 優點
Trie很常用於字典，因為省記憶體
```python
                                    ◎
                                   / \
                                  a   b
                                 /     \
                                n       e 
                               / \       \
                              d   t       a (3)
                             (0)  (1)      \
                                            r (2)
```

**:thumbsup:** 

Implement Trie (Prefix Tree) 經典範例
```python
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
```


```python
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`