solution.md

# 串联所有单词的子串

<p>给定一个字符串&nbsp;<strong>s&nbsp;</strong>和一些长度相同的单词&nbsp;<strong>words。</strong>找出 <strong>s
    </strong>中恰好可以由&nbsp;<strong>words </strong>中所有单词串联形成的子串的起始位置。</p>
<p>注意子串要与&nbsp;<strong>words </strong>中的单词完全匹配，中间不能有其他字符，但不需要考虑&nbsp;<strong>words&nbsp;</strong>中单词串联的顺序。</p>
<p>&nbsp;</p>
<p><strong>示例 1：</strong></p>
<pre><strong>输入：  s =</strong> &quot;barfoothefoobarman&quot;,<strong>  words = </strong>[&quot;foo&quot;,&quot;bar&quot;]<strong><br />输出：</strong>[0,9]<strong><br />解释：</strong>从索引 0 和 9 开始的子串分别是 &quot;barfoo&quot; 和 &quot;foobar&quot; 。输出的顺序不重要, [9,0] 也是有效答案。</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：  s =</strong> &quot;wordgoodgoodgoodbestword&quot;,<strong>  words = </strong>[&quot;word&quot;,&quot;good&quot;,&quot;best&quot;,&quot;word&quot;]<strong><br />输出：</strong>[]</pre>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    vector<int> res;
    string s = "barfoothefoobarman";
    vector<string> words{"foo", "bar"};
    res = sol.findSubstring(s, words);

    for (auto i : res)
        cout << i << " ";
    return 0;
}
```

## 答案

```c
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        if (words.empty() || s.empty())
            return {};
        vector<int> ans;
        int len = words[0].length(), n = words.size(), total = n * len;
        ;
        int l = s.length();
        unordered_map<string, int> list;
        int i, j, left;
        for (i = 0; i < n; i++)
            list[words[i]]++;
        for (i = 0; i <= l - total; i++)
        {
            unordered_map<string, int> window;
            bool flag = true;
            left = i;
            string str;
            while (left - i < total)
            {
                str = s.substr(left, len);
                if (list.count(str) == 1 && window[str] != list[str])
                {
                    window[str]++;
                    left += len;
                }
                else
                {
                    flag = false;
                }
            }
            if (flag)
                ans.push_back(i);
        }
        return ans;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> res;
        if (s.empty() || words.empty())
        {
            return res;
        }
        unordered_map<string, int> ht;
        for (const auto &w : words)
        {
            ht[w]++;
        }
        int len = words[0].length();
        for (int i = 0, j = 0; i < s.length() - words.size() * len + 1; i++)
        {
            unordered_map<string, int> counting;
            for (j = 0; j < words.size(); j++)
            {
                string word = s.substr(i + j * len, len);
                if (++counting[word] > ht[word])
                {
                    break;
                }
            }
            if (j == words.size())
            {
                res.push_back(i);
            }
        }
        return res;
    }
};
```

### B

```c
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        if (words.empty() || s.empty())
            return {};
        vector<int> ans;
        unordered_map<string, int> umap1;
        unordered_map<string, int> umap2;
        int count = 0;
        int left = 0;
        for (string str : words)
            ++umap1[str];
        int len = words[0].size();
        int slen = s.size();
        for (int i = 0; i < len; i++)
        {
            left = i;
            count = 0;
            umap2.clear();
            for (int j = i; j <= slen - len; j += len)
            {
                string temp = s.substr(j, len);
                if (umap1.count(temp))
                {
                    umap2[temp]++;
                    count++;
                    while (umap2[temp] > umap1[temp])
                    {
                        string temp2 = s.substr(left, len);
                        --umap2[temp2];
                        --count;
                        left += len;
                    }
                    if (count == words.size())
                    {
                        ans.push_back(left);
                        --umap2[s.substr(left, len)];
                        --count;
                        left += len;
                    }
                }
                else
                {
                    umap2.clear();
                    count = 0;
                    left = j + len;
                }
            }
        }
        return ans;
    }
};
```

### C

```c
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> result;
        if (words.size() == 0 || s.length() == 0)
            return result;

        map<string, int> words_map;
        int word_len = words[0].length();
        int word_num = words.size();
        if (word_len > s.length())
            return result;
        for (vector<string>::iterator it = words.begin(); it != words.end(); it++)
        {
            if (words_map.count(*it))
                words_map[*it]++;
            else
                words_map[*it] = 1;
        }

        for (int i = 0; i < word_len; i++)
        {
            int left = i, right = i;
            int cur_num = 0;
            map<string, int> s_map;
            string right_str, left_string;
            while (right <= s.length() - word_len)
            {
                right_str = s.substr(right, word_len);

                if (!words_map.count(right_str))
                {
                    right += word_len;
                    left = right;
                    cur_num = 0;
                    s_map.clear();
                }
                else
                {

                    if (!s_map.count(right_str))
                        s_map.insert(pair<string, int>(right_str, 1));
                    else
                        s_map[right_str] += 1;

                    cur_num += 1;
                    right += word_len;

                    if (s_map[right_str] > words_map[right_str])
                    {

                        while (s_map[right_str] > words_map[right_str])
                        {
                            string left_str = s.substr(left, word_len);
                            s_map[left_str]--;
                            cur_num--;
                            left += word_len;
                        }
                    }

                    if (cur_num == word_num)
                    {

                        result.push_back(left);

                        s_map[s.substr(left, word_len)]--;
                        left += word_len;
                        cur_num--;
                    }
                }
            }
        }

        return result;
    }
};
```