題目網址：https://leetcode.cn/problems/design-add-and-search-words-data-structure/

題意：請設計一資料結構, 支持新增單字、搜尋 string 是否和先前新增的單字匹配。

實作 WordDictionary class：

  • WordDictionary()：初始化 instance
  • void addWord(word)：將 word 新增到資料結構中, 之後可以對它進行匹配
  • bool search(word)：如果資料結構中存在 string 和 word 匹配, 則返回 true ; 否則, 返回 false。word 中可能包含一些 ., 每個 . 都可表示成任何一個 char

注意：

  • addWord 中的 word 只由小寫字母所組成
  • search 中的 word 由 . or 小寫字母所組成

Solution：

想法：利用 Trie + DFS, 一旦遇到 ., 就對當前 node 中所有的 child 進行 DFS

class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie {
public:
    TrieNode *root = new TrieNode();

    void insert(string& word){
        TrieNode *cur = root;
        for (const auto& ch : word) {
            const int idx = ch - 'a';

            if (!cur->children[idx]) {
                cur->children[idx] = new TrieNode();
            }

            cur = cur->children[idx];
        }
        cur->isEnd = true;
    }
};

class WordDictionary {
public:
    WordDictionary() {}

    void addWord(string word) {
        trie.insert(word);
    }

    bool search(string word) {
        return dfs(trie.root, word, 0);
    }

private:
    Trie trie;

    bool dfs(TrieNode* node, string& word, int j){
        TrieNode *cur = node;
        for (int i = j; i < word.size(); ++i) {
            if (word[i] == '.') {
                for (const auto& child : cur->children){
                    // 要先判斷 child 是否為 nullptr, i + 1 是因為跳過當前 char
                    if (child && dfs(child, word, i + 1)) {
                        return true;
                    }
                }
                return false;
            }
            else {
                const int idx = word[i] - 'a';
                if (!cur->children[idx]) {
                    return false;
                }
                cur = cur->children[idx];
            }
        }
        return cur->isEnd;
    }
};
  • time：
    • WordDictionary()：$O(1)$
    • addWord(word)：$O(n)$ ➔ 其中 n 為 word.size()
    • search(word)：$O(26^n)$ ➔ worse case : word 中每個 char 皆為 ., 這樣每個 char 都有 26 種可能
  • space：$O(T)$ ➔ $O(26 \cdot T)$, 其中 T 為 trie 中所有的 node 數