Substring with Concatenation of All Words

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

You are given a string,s, and a list of words,words, that are all of the same length. Find all starting indices of substring(s) insthat is a concatenation of each word inwordsexactly once and without any intervening characters.

For example, given: s:"barfoothefoobarman" words:["foo", "bar"]

You should return the indices:[0,9]. (order does not matter).

Thoughts

给一个word list和S，找出S中出现了由所有word list元素拼接而成的substr。判断每个substr是否是words的permutation，自然要用以word为基础步的滑动窗口，这样的滑动窗口可以分别以[0, step - 1]为起点。

Code

/*
 * @lc app=leetcode id=30 lang=cpp
 *
 * [30] Substring with Concatenation of All Words
 *
 * https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
 *
 * algorithms
 * Hard (24.04%)
 * Likes:    606
 * Dislikes: 988
 * Total Accepted:    144.5K
 * Total Submissions: 600.3K
 * Testcase Example:  '"barfoothefoobarman"\n["foo","bar"]'
 *
 * You are given a string, s, and a list of words, words, that are all of the
 * same length. Find all starting indices of substring(s) in s that is a
 * concatenation of each word in words exactly once and without any intervening
 * characters.
 * 
 * Example 1:
 * 
 * 
 * Input:
 * ⁠ s = "barfoothefoobarman",
 * ⁠ words = ["foo","bar"]
 * Output: [0,9]
 * Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar"
 * respectively.
 * The output order does not matter, returning [9,0] is fine too.
 * 
 * 
 * Example 2:
 * 
 * 
 * Input:
 * ⁠ s = "wordgoodgoodgoodbestword",
 * ⁠ words = ["word","good","best","word"]
 * Output: []
 * 
 * 
 */
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        if (s.size() == 0 || words.size() == 0)
            return {};
        const int step = words[0].length(), N = words.size();
        if (step > s.size())
            return {};
        unordered_map<string, int> ifreq;
        for (const auto &w : words)
        {
            if (!ifreq.count(w))
                ifreq[w] = 0;
            --ifreq[w];
        }
        vector<int> res;
        for (int i = 0; i < step; ++i)
        {
            auto freq(ifreq);
            int cur_size = 0;
            for (int j = 0; j < N; ++j)
            {
                const auto w = s.substr(i + j * step, step);
                if (freq.count(w))
                {
                    ++freq[w];
                    if (freq[w] <= 0)
                        ++cur_size;
                }
            }
            if (cur_size == N)
                res.push_back(i);
            int l = i, r = i + step * N;
            while (r <= s.size() - step)
            {
                const auto rw = s.substr(r, step);
                if (freq.count(rw))
                {
                    ++freq[rw];
                    if (freq[rw] <= 0)
                        ++cur_size;
                }
                const auto lw = s.substr(l, step);
                if (freq.count(lw))
                {
                    --freq[lw];
                    if (freq[lw] < 0)
                        --cur_size;
                }
                l += step;
                if (cur_size == N)
                    res.push_back(l);
                r += step;
            }
        }
        return res;
    }
};

Analysis

Errors:

1. l += step;放错位置导致l没有及时前移，res晚了一步

2. r < i + targetCount * step && r < s.length() - step + 1 没写后者

3. r < s.length() - step 少了+1

时间复杂度O(n).