[30. concatenate substrings of all words]

source ： Power button （LeetCode）

describe ：

Given a string s And some of the Same length 's words words . find s It happens that words The starting position of the substring formed by concatenation of all words in .

Pay attention to the relationship between the string and words The words in match exactly , No other characters in the middle , But there's no need to think about words The order in which words are concatenated .

Example 1：

 Input ：s = "barfoothefoobarman", words = ["foo","bar"]
 Output ：[0,9]
 explain ：
 From the index  0  and  9  The first substrings are  "barfoo"  and  "foobar" .
 The order of output is not important , [9,0]  It's also a valid answer .

Example 2：

 Input ：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
 Output ：[]

Example 3：

 Input ：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 Output ：[6,9,12]

Tips ：

• 1 <= s.length <= 10⁴
• s It's made up of lowercase letters
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] It's made up of lowercase letters

Method ： The sliding window

Ideas

remember words The length of is m, words The length of each word in is n,s The length of is ls. First, you need to s Divide into word groups , The size of each word is n （ Except the beginning and end ）. Such division methods include n Kind of , I.e. delete the former i （ i = 0 ∼ n − 1） After two letters , Divide the remaining letters , If there is less than at the end n The letters are also deleted . For this n The resulting word arrays are divided into two groups by using sliding window pairs words Proceed similarly to 「 Letter heterotopic word 」 My search .

Divide into word groups , A window contains s Middle front m Word , With a hash table differ Indicates the word frequency and... In the window words The difference in the frequency of words in . initialization differ when , Words that appear in the window , Every time , The corresponding value increases 1, Appear in the words The words in , Every time , The corresponding value decreases 1. Then move the window to the right , A word will be added to the right , A word will be moved out on the left , Also on differ Update accordingly . When the window moves , If it appears differ The median 0 The number of keys of is 0, It means the word frequency and words The frequency of Chinese words is the same , The left endpoint of the window is a starting position to be found . The methods of division are n Kind of , do n After sliding the window a second time , You can find all the starting positions .

Code ：

class Solution {
    
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
    
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
    
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
    
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
    
                if (--differ[word] == 0) {
    
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
    
                if (start != i) {
    
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
    
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
    
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
    
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};

Execution time ：56 ms, In all C++ Defeated in submission 72.93% Users of
Memory consumption ：33.1 MB, In all C++ Defeated in submission 34.82% Users of
author：LeetCode-Solution