🔗 🟡 676. Implement Magic Dictionary

tags: `Weekly Contest 25` `字串(String)` `雜湊表(Hash Table)` `DFS` `字典樹(Trie)` `設計(Design)`

題意

設計一個資料結構，使用一個單字列表初始化，列表中的單字 互不相同 。

給定一個字串，你要判斷能否僅改變這個字串中的一個字元，使其與資料結構中的任何單字匹配。

實作 MagicDictionary 類別：

MagicDictionary() 初始化物件。
void buildDict(String[] dictionary) 用一個不同字串的陣列來設定資料結構。
bool search(String searchWord) 如果能將 $searchWord$ 的一個字元改變成資料結構中的任何字串則回傳 true，否則回傳 false。

思路：字典樹(Trie) + DFS

首先整理題意，題目要求我們設計一個可以判斷給定字串 $searchWord$ 是否能通過 修改一個字元 變成字典中的任意單字的資料結構。若我們逐個考慮 $searchWord$ 的每個字元，則每個字元都可以選擇修改或不修改，且最後需要恰好修改一次。為了達到這個目的，我們可以使用字典樹(Trie) 來高效地存儲和檢索字典中的單字，並結合深度優先搜索(DFS) 來實現這個判斷過程。

在 buildDict 時按照正常的方式將字串存入字典樹，但是在 search 時，我們可以使用 深度優先搜索(DFS) 來實現這個判斷過程。

構建一個 DFS 函數 dfs(node, i, modified) ，其中 node 表示當前層的字典樹，i 表示字串 $searchWord$ 的第 $i$ 個字元，modified 表示是否已經修改過某個位置的字元。

當 i == len(searchWord) 時，如果 modified == true 且 node 的子節點是結尾節點，則返回 true；否則返回 false。
由於每個字元都可以選擇修改或不修改，因此分別考慮兩種情況：
- 若 searchWord[i] 在 node 的子節點中，則可以不用修改當前字元，遞迴考慮 dfs(node.child[searchWord[i]], i+1, modified) ，若其結果為 true 則返回 true；
- 否則則考慮修改當前字元，枚舉當前位置可以修改的字元 ch，遞迴考慮 dfs(node.child[ch], i+1, true) ，若其結果為 true 則返回 true。
- 若以上兩種情況都沒有匹配到，則返回 false。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot l + \Sigma \cdot l^2)$ $O (n \cdot l + Σ \cdot l^{2})$ ，其中 $n$ $n$ 是字串陣列 $dictionary$ $d i c t i o na ry$ 的長度， $l$ $l$ 是 $dictionary[i]$ $d i c t i o na ry [i]$ 的平均長度、 $\Sigma$ $Σ$ 是字元集合的大小，本題中為 $26$ $26$ 。
- buildDict 的時間複雜度為 $\mathcal{O}(n \cdot l)$ ，其中 $n$ 是字串陣列 $dictionary$ 的長度， $l$ 是 $dictionary[i]$ 的平均長度。
- search 的時間複雜度為 $\mathcal{O}(\Sigma \cdot l^2)$ ，由於修改可以發生在每一個位置，且最多有 $\Sigma$ 種字元可以修改，因此總共有 $O(\Sigma \cdot l)$ 種狀態，而每個狀態需要 $O(l)$ 的時間驗證，因此共需 $\mathcal{O}(\Sigma \cdot l^2)$ 的時間。
空間複雜度： $\mathcal{O}(n \cdot l)$ ，字典樹所需的空間。

註：實際的時間複雜度會比上述的時間複雜度低，因為發生修改時並不會總是有 $\Sigma$ 種字元可以修改，且部分狀態可能不存在於字典樹中，可以透過剪枝來處理掉。

class Trie:  # Trie Node
    def __init__(self):
        self.child = {}
        self.is_end = False

class MagicDictionary:

    def __init__(self):
        self.root = Trie()

    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            cur = self.root
            for ch in word:
                if ch not in cur.child:
                    cur.child[ch] = Trie()
                cur = cur.child[ch]
            cur.is_end = True

    def search(self, searchWord: str) -> bool:
        def dfs(node: Trie, i: int, modified: bool) -> bool:
            if i == len(searchWord):
                return modified and node.is_end

            if searchWord[i] in node.child:  # 不修改當前位置的字母
                if dfs(node.child[searchWord[i]], i + 1, modified):
                    return True

            if not modified:  # 嘗試修改當前位置的字母，但只能修改一次
                for ch in node.child:  # 只需要考慮在 Trie 中存在的字母即可
                    if ch == searchWord[i]:
                        continue
                    if dfs(node.child[ch], i + 1, True):
                        return True

            return False

        return dfs(self.root, 0, False)

class Trie {
public:
    bool is_end;
    vector<Trie*> child;
    Trie() : is_end(false), child(vector<Trie*>(26, nullptr)) {}
};

class MagicDictionary {
public:
    Trie* root;
    MagicDictionary() {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary) {
        for (string& word : dictionary) {
            Trie* node = root;
            for (char& ch : word) {
                if (node->child[ch - 'a'] == nullptr)
                    node->child[ch - 'a'] = new Trie();
                node = node->child[ch - 'a'];
            }
            node->is_end = true;
        }
    }
    
    bool search(string searchWord) {
        function<bool(Trie*, int, bool)> dfs = [&](Trie* node, int i, bool modified) {
            if (i == searchWord.size()) return modified && node->is_end;
            int ch = searchWord[i] - 'a';
            if (node->child[ch] != nullptr) { // 不修改當前位置的字母
                if (dfs(node->child[ch], i + 1, modified)) return true;
            }
            if (!modified) { // 嘗試修改當前位置的字母，但只能修改一次
                for (int j = 0; j < 26; j++) {
                    if (j == ch || node->child[j] == nullptr) continue;
                    if (dfs(node->child[j], i + 1, true)) return true;
                }
            }
            return false;
        };
        return dfs(root, 0, false);
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant, colors, backlight, bright, soft lighting, dreamy atmosphere, orange tone, (1girl, solo), long hair, looking at viewer, gentle smile, bangs, black hair, brown eyes, standing, sleeveless, indoors, blunt bangs, bag, sleeveless dress, handbag, dress, (orange dress), in the library, library, bookshelves, warm light filtering through windows, cozy ambiance, soft shadows, detailed background, vintage decor, scattered books, wooden furniture