題目網址：https://leetcode.cn/problems/index-pairs-of-a-string/

題意：給一 string text 和 string list words, 求所有 index pair 使得 text[i~j] 出現在 words 中。

Solution 1：

想法：暴力搜尋法

class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        const int m = text.size();
        vector<vector<int>> res;
        unordered_set<string> wordSet(words.begin(), words.end());

        for (int start = 0; start < m; ++start) {
            for (int end = start; end < m; ++end) {
                const string cur = text.substr(start, end - start + 1);
                if (wordSet.find(cur) != wordSet.end()) {
                    res.emplace_back(vector<int>{start, end});
                }
            }
        }

        return res;
    }
};

令總共有 n 個 word, 其中 $w_i$ 代表 words[i] 的長度, 且 text 之長度為 m

  • time：$O(m^2 \cdot \displaystyle\sum_{i=1}^{n}w_i)$ ➔ 因為 c++ 的 find() 不是用 KMP 實作的
    • $O(m^2)$：每次以 start 為起點往後遍歷, 取 text[start:end] 然後去判斷是否在 wordset 中
      • $m + (m-1) + (m-2) + … + 1$ = $\dfrac{(m+1)\cdot m}{2}$
    • $O(\displaystyle\sum_{i=1}^{n}w_i)$：每次判斷 text[start:end] 是否在 wordset 中
  • space：$O(\displaystyle\sum_{i=1}^{n}w_i)$ ➔ wordset

Solution 2：

想法：利用 Trie(prefix tree), 可參考 208. Implement Trie (Prefix Tree)

class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false; // 預設每個 char 不為 end
};

class Trie {
private:
    TrieNode *root;

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

    void insert(const string& word){
        TrieNode *p = root;

        for (const auto& c : word) {
            const int i = c - 'a';
            if (!p->children[i]) {
                p->children[i] = new TrieNode();
            }
            p = p->children[i];
        }
        p->isEnd = true; // 將最後一個 char 設為 end
    }

    vector<vector<int>> search(const string& text){
        const int m = text.size();
        vector<vector<int>> res;

        for (int start = 0; start < m; ++start) {
            TrieNode *p = root;
            for (int end = start; end < m && p != nullptr; ++end) {
                p = p->children[text[end] - 'a'];
                if (p && p->isEnd) {
                    res.emplace_back(vector<int>{start, end});
                }
            }
        }

        return res;
    }
};

class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        Trie trie;
        for (const auto& word : words) {
            trie.insert(word);
        }
        return trie.search(text);
    }
};

令總共有 n 個 word, 其中 $w_i$ 代表 words[i] 的長度, 且 text 之長度為 m

  • time：$O(\displaystyle\sum_{i=1}^{n}w_i + m^2)$
    • $O(\displaystyle\sum_{i=1}^{n}w_i)$ : insert 所有 word 到 Trie 中
    • $O(m^2)$ : 每次以 start 為起點往後遍歷, 判斷 text[start:end] 是否在 Trie 中
      • $m + (m-1) + (m-2) + … + 1 =$ $\dfrac{(m+1)\cdot m}{2}$
  • space：$O(26 \cdot \displaystyle\sum_{i=1}^{n}w_i)$ ➔ worse case : 每個 word 的 prefix 皆不重覆
    • 總共 n 個 word, 每一個 word 有 $w_i$ 個 node, 而每個 node 又有 26 個 children