# 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.
# Code (Python)
Approach 1:
import collections
class Solution:
def findSubstring(self, s, words):
# http://www.cnblogs.com/zuoyuan/p/3779978.html
# time: O(len(S) * num_of_words)
result = []
numWords = len(words)
lenWords = len(words[0])
# word_table remembers words -- will use word_table as a reference
word_table = collections.defaultdict(int)
for word in words:
word_table[word] += 1
# for each index of s, check if it's valid
for i in range(len(s) - numWords * lenWords + 1):
table = collections.defaultdict(int)
wordcount = 0
while wordcount < len(words):
new_word = s[i + lenWords * wordcount : i + lenWords * (wordcount + 1)]
# violates "without any intervening characters"
if new_word not in word_table:
break
table[new_word] += 1
# violates "exactly once"
if table[new_word] > word_table[new_word]:
break
wordcount += 1
if wordcount == len(words):
result.append(i)
return result
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[0].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;
}
getAllPermutations(words, head+1);
unordered_set<string> visited;
for (int i = head + 1; i < words.size(); ++i)
{
if (words[head] == words[i] ||
visited.find(words[i]) != visited.end())
continue;
visited.insert(words[i]);
std::swap(words[head], words[i]);
getAllPermutations(words, head+1);
std::swap(words[head], 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[0].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;
}
};