# LeetCode题目：Substring with Concatenation of All Words

Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: “barfoothefoobarman”
L: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).

```class Solution {
public:
vector findSubstring(string S, vector &L) {
map words;
map curStr;
for(int i = 0; i < L.size(); ++i)
++words[L.at(i)];
int N = L.size();
vector ret;
if(N <= 0)   return ret;
int M = L.at(0).size();
for(int i = 0; i <= (int)S.size()-N*M; ++i)
{
curStr.clear();
int j = 0;
for(j = 0; j < N; ++j)
{
string w = S.substr(i+j*M, M);
if(words.find(w) == words.end())
break;
++curStr[w];
if(curStr[w] > words[w])
break;
}
if(j == N)  ret.push_back(i);
}
return ret;
}
};
```

```class Solution {
public:
vector findSubstring(string S, vector &L) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector result;
if(L.size() == 0) return result;
const int wsize = L[0].size();
if(wsize == 0) return result;
//const int minSize = wsize * L.size();
const int notfound = -1;
vector pos(L.size(),notfound);
int si = 0;
while(S.size() - si >= wsize) {
vector mwis;
string possibleword = S.substr(si,wsize);
for(int wi = 0 ; wi < L.size(); ++wi) {
if(possibleword == L[wi]) {
mwis.push_back(wi);
}
}
int matchwordi = notfound;
if(mwis.size() > 0) {
matchwordi = mwis[0];
for(int i = 1 ;pos[matchwordi] != notfound &&  i < mwis.size(); ++i) {
if(pos[mwis[i]] < pos[matchwordi]) {
matchwordi = mwis[i];
}
}
}
if(matchwordi == notfound) {
//no match word found, clear all the pos
for(int i = 0 ; i < pos.size(); ++i) {
pos[i] = notfound;
}
++si;
} else {
//found one
if(pos[matchwordi] != notfound) {
//if this word is already matched,
// clear all the word found before it's old position
int prepos = pos[matchwordi];
for(int i = 0; i < pos.size(); ++i) {
if(pos[i] <= prepos) {
pos[i] = notfound;
}
}
}
pos[matchwordi] = si;

//check if all the word is found
{
int minindex = S.size();
for(int i = 0 ; minindex != notfound && i < pos.size(); ++i) {
if(pos[i] < minindex)
minindex = pos[i];
}
if(minindex != notfound) {
//found valid match for all words
result.push_back(minindex);
}
}

si += wsize;
}
}
return result;
}
};
```

## “LeetCode题目：Substring with Concatenation of All Words”上的12条回复

woodpig说：

“一个长度为M*N的子串在S上从左到右平移，每个位置上，直接去判断是不是每一个L中的单词都出现了一次。”这是一个必要条件，但不是充分条件阿。比如S中几个字母和L中一个string顺序不同

”for(int i = 0; i <= (int)S.size()-N*M; ++i) “

Littlefucker说：

cong说：

li说：

0: 0, k, 2k, 3k …
1: 1, k+1, 2k+1, 3k+1…
2: 2, k+2, 2k+2, …

fredfsh说：

fredfsh说：

fredfsh说：