題目網址：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

題意：給一 string s 和一些長度相同的單字 words。返回 s 中恰好可以由 words 中所有單字串聯而成的 substring 之起始位置。

注意：substring 要與 words 中的單字完全相同, 中間不可參雜其他 char, 而單字串聯的順序可以是任意的。

Solution：

想法：利用 Sliding Window

  • 由於單字串聯的順序可以是任意的, 故利用 freqs 來記錄 words 中每個單字的出現次數
  • 以 i 為起點, 往後取 wordsNum 個單字
    • 用 cur 來記錄當前 substring 中每種單字的出現次數
    • 每個 word 的開頭 = i + j * wordLen, 其中 j 表示以 i 為起點目前取到第幾個單字
    • 若 word 不存在於 freqs 中, 則代表當前 substring 不符合
      ➔ 故 i 往下一個嘗試
    • 若 word 在 cur 中的次數 > 該 word 在 freqs 中的次數, 則代表當前 substring 不符合
      ➔ 故 i 往下一個嘗試
    • 若 j == wordsNum - 1, 則代表以 i 為起點往後取的每個 word 都存在於 words 中
      總共取了 wordsNum 個 word, 且每個 word 皆沒超過 freqs 中對應的個數
      ➔ 代表每個 word 都恰好取了 freqs[word] 次
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        const int n = s.size();
        int wordNum = words.size(), wordLen = words[0].size();

        if (wordNum * wordLen > n) {
            return {};
        }

        unordered_map<string, int> freqs;
        for (const auto& word : words) {
            ++freqs[word];
        }

        vector<int> res;

        for (int i = 0; i < n - wordNum * wordLen + 1; ++i) { // 遍歷所有可能的起點
            unordered_map<string, int> cur;

            for (int j = 0; j < wordNum; ++j) { // 依序取出當前 substring 中每個的 word
                string word = s.substr(i + j * wordLen, wordLen);

                // word 不存在 freqs 中
                if (freqs.find(word) == freqs.end()) {
                    break;
                }

                ++cur[word];

                // word 超過需要的次數
                if (cur[word] > freqs[word]) {
                    break;
                }

                // 以 i 為起點往後取的每個 word 都存在於 words 中
                // 總共取了 wordsNum 個 word, 且沒超過都 freqs 中對應的個數
                // 代表每個 word 都恰好取了 freqs[word] 次
                if (j == wordNum - 1) {
                    res.emplace_back(i);
                }
            }
        }
        
        return res;
    }
};
  • time：$O(n \cdot wordsNum \cdot wordLen)$ ➔ 每次以 i 為起點, 去取 wordsNum 個 word, 而每個 word 長度為 wordLen
  • space：$O(wordsNum \cdot wordLen)$ ➔ freqs 保存所有 word