# 串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s
中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入： s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
vector res;
string s = "barfoothefoobarman";
vector words{"foo", "bar"};
res = sol.findSubstring(s, words);
for (auto i : res)
cout << i << " ";
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
vector findSubstring(string s, vector &words)
{
if (words.empty() || s.empty())
return {};
vector ans;
int len = words[0].length(), n = words.size(), total = n * len;
;
int l = s.length();
unordered_map list;
int i, j, left;
for (i = 0; i < n; i++)
list[words[i]]++;
for (i = 0; i <= l - total; i++)
{
unordered_map 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
```cpp
class Solution
{
public:
vector findSubstring(string s, vector &words)
{
vector res;
if (s.empty() || words.empty())
{
return res;
}
unordered_map 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 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
```cpp
class Solution
{
public:
vector findSubstring(string s, vector &words)
{
if (words.empty() || s.empty())
return {};
vector ans;
unordered_map umap1;
unordered_map 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
```cpp
class Solution
{
public:
vector findSubstring(string s, vector &words)
{
vector result;
if (words.size() == 0 || s.length() == 0)
return result;
map words_map;
int word_len = words[0].length();
int word_num = words.size();
if (word_len > s.length())
return result;
for (vector::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 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(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;
}
};
```