211. Design Add and Search Words Data Structure

──────────────────────────────────────────────────────────────────────

211. Design Add and Search Words Data Structure

設計一個資料結構，支援 addWord 加入單字、search 查詢單字，而查詢字串裡的 . 可以匹配任何一個字元。

思路

這一題比較特別，需要模糊比對搜尋的字串，主要也要用到 Trie，除了紀錄字元以外，可以用特殊的字元記錄額外資訊。

Trie 用巢狀 dict 就夠

不用另外開節點類別，一層 dict 就是一個節點，key 是字元、value 是下一層：

addWord("bad") ->  {'b': {'a': {'d': {'$': True}}}}

'$' 就是那個「特殊的字元」—— 它不是任何字元的分支，而是標記這裡可以結束。沒有它就分不出「bad 有被加進去」和「bad 只是 badly 的前綴」。也因為 '$' 混在同一層 dict 裡，走訪分支時要記得把它跳過。

. 是唯一需要遞迴的地方

沒有 . 的話，search 就是一路 node = node[char] 走下去，完全不用遞迴。

碰到 . 才會分岔：這一層的每個分支都要試一次，任何一條成功就成功。所以遞迴的意義是「從下一個字元開始，在這個分支底下繼續找」。

嘗試完所有分支都失敗之後，程式會往下走到 if char not in node。因為 . 不會是 trie 裡的 key，這裡必定回傳 False —— 剛好就是「所有分支都試過了，沒有一條成立」。

解題方向

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}

    def addWord(self, word: str) -> None:
        node = self.trie
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['$'] = True


    def search(self, word: str) -> bool:
        def search_in_node(start, node) -> bool:
            for i in range(start, len(word)):
                char = word[i]
                if char == '.':
                    for x in node:
                        if x != '$' and search_in_node(i + 1, node[x]):
                            return True
                if char not in node:
                    return False
                else:
                    node = node[char]
            return '$' in node
        return search_in_node(0, self.trie)


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

遞迴傳的是索引而不是 word[i+1:]。這一點值得留意：. 會讓每一層分岔成最多 26 條，如果每條都切一份剩餘字串，光是複製就會乘上分支數。改成傳 i + 1、迴圈用 range(start, len(word))，其他邏輯一行都不用動。

複雜度

設 $L$ 是單字長度、$N$ 是已加入的單字數、$\mathrm{\Sigma }$ 是字元集大小（小寫英文是 26）。

addWord

• 時間 $O(L)$ — 一個字元走一層
• 空間 $O(L)$ — 最壞情況每個字元都要開一層新的 dict

search

• 時間 沒有 . 時 $O(L)$；全部都是 . 時最壞 $O({\mathrm{\Sigma }}^L)$ — 每一層都要展開所有分支。實際上會被 trie 裡真正存在的分支數擋住，所以上界也可以寫成 $O(N\times L)$
• 空間 $O(L)$ — 遞迴深度最多就是字串長度

整體空間 $O(N\times L)$ — 所有單字的字元總數，共用前綴的部分會合併掉。