[LeetCode] 30. Substring with Concatenation of All Words

• 這一題與 567 類似，差別是將字元比較改成字串比較。
• 注意因為字串比較不一定是從 0 開始，所以還要多一個 for start in range(0, wordLen) 的迴圈來調整起始位置

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> cnt1, cnt2;
        for (const auto& word : words) cnt1[word]++;
        int wordLen = words[0].size();
        int k = words.size();
        vector<int> res;
        if (s.size() < wordLen * k) return res;
        for (int start = 0; start < wordLen; start++) {
            cnt2.clear();
            int valid = 0;
            for (int i = start; i < k * wordLen; i += wordLen) {
                string sin = s.substr(i, wordLen);
                if (cnt1.count(sin) && ++cnt2[sin] == cnt1[sin]) valid++;
            }
            if (valid == cnt1.size()) res.push_back(start);
            for (int i = start + k * wordLen; i < s.size(); i += wordLen) {
                string sin = s.substr(i, wordLen);
                if (cnt1.count(sin) && ++cnt2[sin] == cnt1[sin]) valid++;
                string sout = s.substr(i-k*wordLen, wordLen);
                if (cnt1.count(sout) && cnt2[sout]-- == cnt1[sout]) valid--;
                if (valid == cnt1.size()) res.push_back(i-(k-1)*wordLen);
            }
        }
        return res;
    }
};