今天要看的是 Trie tree。

字典樹(trie tree)如下圖所示，擁有相同前綴的單字也會共享部分路徑，然後在出現差異的部分開始分岔出去。因此搜尋時從上往下走，如果走到某一部找不到相關的內容，就表示該元素不存在。

圖片出處：維基百科

208. Implement Trie (Prefix Tree) 這題是基本的實作題，單純把 trie 刻出來就可以了。特別需要留意的是，當一個單字結束時，要特別打上 tag 來做辨識，例如我們先加入了 apple 這個單字，如果這時候要搜 app，由於走到最後時找不到 tag，因此就可以判斷該單字不存在。

另外，下面的實作方法是單字的每個 char 都開一個 dict 往下。其實有想過在初期時，是不是可以直接把整個單字（或者部分單字）當成 key（像上圖所示），等到出現了有相同 prefix 的單字後才去做 merge。不過這麼做要不停的 detect & merge，不確定是否能有更好的效能，複雜度也更高因此最後沒有採用。

class Trie:
    def __init__(self):
        self.d = {}

    def insert(self, word: str) -> None:
        d = self.d
        for i in word:
            if i in d:
                d = d[i]
            else:
                d[i] = {}
                d = d[i]
        d[1] = 1

    def search(self, word: str) -> bool:
        d = self.d
        for i in word:
            if len(d) == 0:
                return False
            if i not in d:
                return False
            d = d[i]
        return True if 1 in d else False

    def startsWith(self, prefix: str) -> bool:
        d = self.d
        for i in prefix:
            if len(d) == 0:
                return False
            if i not in d:
                return False
            d = d[i]
        return True

• Trie tree
  • 208. Implement Trie (Prefix Tree)

• Total Count: 7