# 30 - Substring with Concatenation of All Words

解法一 - 暴力法

我們可以把每個 index 當作可能的起點，然後從這個起點一直往後抓 word 長度的 token 來比較，如果發現已經不在 words 裡了，那就從下一個起點 index 重新開始找，可惜這麼做會 TLE，不過還是記一下 code。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        if(s.empty() || words.empty()) return res;

        int idx = 0, win_sz = words[0].size();
        while(idx < s.length()) {
            // Prepare a set for checking
            unordered_map<string, int> table;
            for(auto w: words) { 
                if(table.find(w) != table.end())
                    table[w] += 1;
                else
                    table[w] = 1;
            }

            // Start checking from idx
            int k, l;
            for(k=0, l=idx; k<words.size(); k++, l+=win_sz) {
                string tok = s.substr(l, win_sz);
                if(table.find(tok) != table.end()) {
                    table[tok]--;
                }
                else
                    break;
            }

            // Determine if idx is a valid ans position
            bool pushFlag = true;
            for ( auto it = table.begin(); it != table.end(); ++it )
                if(it->second != 0) pushFlag = false;

            if(pushFlag)
                res.push_back(idx);

            // Increment idx
            idx ++;
        }

        return res;
    }
};

// every time check a window, if consecutive windows contain each

解法二 - 用兩個 Hash table 優化解決過程

解法一裡面有兩個效率很低的地方：

1. 每檢查一個新的 idx，就得重新建立一次 table

2. 為了確認 idx 是否 valid，得 go through 一次 table 看是否所有 value 都是 0

我們可以用兩個 Hash Table，減少解法一裡面的冗餘計算：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> indexes;
        if(s.empty() || words.empty()) return indexes;

        // Use counts to record the expected times of each word
        unordered_map<string, int> counts;
        for (string word : words)
            counts[word]++; 

        int n = s.length(), num = words.size(), len = words[0].length();

        // we check for every possible position of i. 
        // Once we meet an unexpected word 
        // or the times of some word is larger than its expected times, 
        // we stop the check. 
        // If we finish the check successfully, push i to the result indexes.
        for (int i = 0; i < n - num * len + 1; i++) {
            // Use seen to record the times we have seen
            unordered_map<string, int> seen;

            int j = 0;
            for (; j < num; j++) {
                string word = s.substr(i + j * len, len);
                if (counts.find(word) != counts.end()) {
                    seen[word]++;
                    if (seen[word] > counts[word])
                        break;
                }
                else break;
            }

            if (j == num) indexes.push_back(i);
        }

        return indexes;
    }
};

Reference

https://leetcode.wang/leetCode-30-Substring-with-Concatenation-of-All-Words.html