## # 30. Substring with Concatenation of All Words

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: []
``````

### # Solution

Approach 1: Scan the string s to match each word and the total number of the words.

Approach 2: (Time Limit Exceeded) First get all permutations of words, and then scan the string s to match each permutation.

Approach 1:

Approach 2:

### # Code (C++)

Approach 1:

``````// Scan the string s to match each word and the total number of the words.
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
int wordsSize = words.size();
if (wordsSize == 0 || s.size() == 0)
return res;
int wordLen = words.size();
unordered_map<string,int> wordsMap;
for (int i = 0; i < words.size(); ++i)
{
wordsMap[words[i]]++;
}
for (int i = 0; i + wordLen * wordsSize <= s.size(); ++i)
{
unordered_map<string,int> sMap;
int j = 0;
for (; j <= wordsSize; ++j)
{
string curr = s.substr(i + j * wordLen, wordLen);
if (wordsMap.find(curr) == wordsMap.end())
break;
sMap[curr]++;
if (sMap[curr] > wordsMap[curr])
break;
}
if (j == wordsSize)
res.push_back(i);
}
return res;
}
};
``````

Approach 2:

``````// Time Limit Exceeded.
// First get all permutations of words, and then scan the string s to match each permutation.
class Solution {
private:
unordered_set<string> p;
void getAllPermutations(vector<string>& words, int head) {
if (head == words.size() - 1)
{
ostringstream oss;
for (int i = 0; i < words.size(); ++i)
{
oss << words[i];
}
p.insert(oss.str());
return;
}
unordered_set<string> visited;
for (int i = head + 1; i < words.size(); ++i)
{
visited.find(words[i]) != visited.end())
continue;
visited.insert(words[i]);
}
}
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
int wordsSize = words.size();
if (wordsSize == 0 || s.size() == 0)
return res;
int wordLen = words.size();
getAllPermutations(words, 0);
for (int i = 0; i + wordLen * wordsSize <= s.size(); ++i)
{
if (p.find(s.substr(i, wordLen * wordsSize)) != p.end())
res.push_back(i);
}
return res;
}
};
``````