題目網址：https://leetcode.cn/problems/prefix-and-suffix-search/

題意：設計一個可以透過 prefix 和 suffix 來搜尋單字的特殊字典。

請實現 WordFilter class：

  • WordFilter(string[] words)：使用 word 來初始化 WordFilter
  • f(string pref, string suff)：返回字典中具有前綴 prefix 和後綴 suffix 單字的 index。若不只一個 index 滿足要求, 則返回最大的 index。若不存在這樣的單字, 則返回 1。

其中, words[i]、pref、suff 僅由小寫字母所組成。

Solution 1：

想法：利用 hash table 去儲存每個單字所有可能的 prefix_suffix 組合, 並對應到該單字的 index。若有單字有相同的 prefix_suffix 組合, 則後面的單字會覆蓋掉前面的單字之 index

  • 紀錄該單字的 prefixes、suffixes 長度為 n + 1, 其中 n 為該單字的長度, 因為要加上 empty string

    e.g. word = ["abc"], 可得到：

    • prefixes = ["", "a", "ab", "abc"]
    • suffixes = ["", "c", "bc", "abc"]
    • 所有的 prefix_suffix 組合總共有 (3+1) x (3+1) = 16 種

  • 建立 prefixes、suffixes 需 $O(n^2)$ time, 因為 string c = a + b, 需 $O(a.size() + b.size())$
    ➔ 建立 prefix = suffix = 1 + 2 + ... + n = $O(n^2)$

class WordFilter {
public:
    WordFilter(vector<string>& words) {
        int idx = 0;
        for (const auto& word : words) {
            const int n = word.size();
            vector<string> prefixes(n + 1, "");
            vector<string> suffixes(n + 1, "");

            // 需 O(n^2) time, 因為 string c = a + b, 需 O(a.size() + b.size()) time
            for (int i = 0; i < n; ++i) {
                prefixes[i + 1] = prefixes[i] + word[i];
                suffixes[i + 1] = word[n - 1 - i] + suffixes[i];
            }

            // 若有相同的 prefix_suffix, 則後面的 word 會覆蓋掉前面的 word 之 idx
            // 建立所有的 prefix_suffix 組合需 O(n^3) time
            for (const auto& prefix : prefixes) {
                for (const auto& suffix : suffixes) {
                    filter[prefix + "_" + suffix] = idx; // 需 O(n) time
                }
            }

            ++idx; // 下一個 word 之 idx 要加一
        }
    }

    int f(string pref, string suff) {
        const string key = pref + "_" + suff;
        const auto it = filter.find(key);

        if (it != filter.end()) {
            return it->second; // 返回 idx
        }

        return -1;
    }

private:
    unordered_map<string, int> filter;
};
  • time：
    • WordFilter()：$O(\sum\limits_{i = 0}^{n-1}{w_i^3})$, 其中 $w_i$ 為單字長度, 總共有 $n$ 個單字
      • 每個單字建立 prefixes, suffixes 需 $O(w_i^2)$, 總共需花 $O(\sum\limits_{i = 0}^{n-1}{w_i^2})$
      • 每個單字總共有 $O(w_i^2)$ 種 prefix_suffix 組合, 而每一種組合需花 $O(w_i)$ 建立對應的 key, 也就是 prefix + "_" + suffix。因此每個單字需花 $O(w_i^3)$ 建立所有的 prefix_suffix 組合, 總共需花 $O(\sum\limits_{i = 0}^{n-1}{w_i^3})$
    • f()：$O(p + s)$, 建立 key 的時間複雜度, 其中 $p$ 為 pref 長度, $s$ 為 suff 長度
  • space：$O(\sum\limits_{i = 0}^{n-1}{w_i^3})$ ➔ filter, 每個單字有 $O(w_i^2)$ 種 prefix_suffix 組合, 而每一種又有長度為 $O(w_i)$ 的 key, 因此每個單字需 $O(w_i^3)$, 總共需 $O(\sum\limits_{i = 0}^{n-1}{w_i^3})$

Solution 2：

想法：利用 Trie, 本題最大的困難點在於不知如何搜尋以 suffix 結尾的單字, 對於每個單字 word, 我們把所有可能的 suffixes_word 組合 insert 到 trie 中(因為 word 本身滿足 prefix 順序)。最後, 用 suff_pref 來做搜尋

e.g. word = ["apple"] 可產生以下 suffixes_word 組合：
["_apple", "e_apple", "le_apple", "ple_apple", "pple_apple", "apple_apple"]

另外, 使用 { 作為分隔符, 用來隔開 prefix 和 suffix, 因為 { 在 ASCII 中恰好是 z 的下一個, 這樣就不用額外寫判斷式

class TrieNode{
public:
    TrieNode* children[27] = {nullptr}; // 多一個分割符號 "{"
    int idx = -1; // 要記錄該 word 在 words 中的 idx
};

class Trie{
public:
    TrieNode *root;

    Trie() : root(new TrieNode()) {}

    void insert(const string& word, int& idx){
        TrieNode *node = root;
        for (const auto& ch : word) {
            const int i = ch - 'a';
            if (!node->children[i]) {
                node->children[i] = new TrieNode();
            }
            node = node->children[i];
            node->idx = idx; // 紀錄 idx
        }
    }

    // 若存在 prefix, 則返回 idx。否則, 返回 -1
    int startsWith(const string& prefix){
        TrieNode *node = find(prefix);
        return (node != nullptr) ? node->idx : -1;
    }

private:
    // 若 prefix 不在 trie 中, 則返回 nullptr; 否則, 返回 end node 之 ptr
    TrieNode* find(const string& prefix){
        TrieNode *node = root;

        for (const auto& ch : prefix) {
            const int i = ch - 'a';
            if (!node->children[i]) {
                return nullptr;
            }
            node = node->children[i];
        }

        return node;
    }
};

class WordFilter {
public:
    WordFilter(vector<string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            const int len = words[i].size();
            string key = "{" + words[i]; // { 作為分割符
            trie.insert(key, i); // suffix 為空的組合

            // 將所有 suffixes_word 組合 insert 到 trie 中(suffix 非空)
            // 需花 O(len^2) time
            for (int j = 0; j < len; ++j) {
                key = words[i][len - 1 - j] + key;
                trie.insert(key, i);
            }
        }
    }

    int f(string pref, string suff) {
        // trie 中搜尋 suff + "{" + pref
        return trie.startsWith(suff + "{" + pref);
    }

private:
    Trie trie;
};
  • time：
    • WordFilter()：$O(\sum\limits_{i = 0}^{n-1}{w_i^2})$, 其中 $w_i$ 為單字長度, 總共有 $n$ 個單字
      • 每個單字建立所有的 suffixes_word 組合需 $O({w_i}^2)$, 總共需 $O(\sum\limits_{i = 0}^{n-1}{w_i^2})$
    • f()：$O(p + s)$, 其中 $p$ 為 pref 的長度, $s$ 為 suff 的長度
      • 建立 string suff_pref
      • 在 trie 中搜尋 suff_pref
  • space：$O(\sum\limits_{i = 0}^{n-1}{w_i}^2)$ ➔ trie, 每個單字有 $O(w_i)$ 種 suffixes_word 組合, 而每一種長度為 $O(w_i)$。因此 在 worse case 中(沒有任何共用 prefix 的情況下)每個單字建立所有的 suffixes_word 組合需 $O(w_i^2)$, 總共需 $O(\sum\limits_{i = 0}^{n-1}{w_i^2})$