LC 30. Substring with Concatenation of All Words

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int sz = words.size();
        int m = words[0].size();
        int n = s.size();
        vector<int> ans;

        unordered_map<string, int> Map;
        for (int i = 0; i < sz; i++) Map[words[i]] += 1;

        for (int i = 0; i < m; i++) {
            vector<string> arr;
            for (int j = i; j < n; j += m) {
                string str = s.substr(j, m);
                arr.push_back(str);
            }
            unordered_map<string, int> have;
            int cnt = 0;
            int l = 0, r = 0;
            while (r < arr.size()) {
                if (!Map.count(arr[r])) {
                    while (l < r) have[arr[l++]] -= 1;
                    cnt = 0;
                    r += 1;
                    l = r;
                    continue;
                }
                while (have[arr[r]] >= Map[arr[r]]) {
                    have[arr[l]] -= 1;
                    cnt -= 1;
                    l += 1;
                }
                have[arr[r]] += 1;
                cnt += 1;
                if (cnt == sz) {
                    ans.push_back(i + l * m);
                }
                r += 1;
            }
        }

        return ans;
    }
};

Time Complexity: O(n * word[i].length)
Space: O(n)

可以發現我們如果將起點分別從 0 ~ word[i].length 進行切割就可以考量到所有的切割狀況。