# LeetCode题目：Substring with Concatenation of All Words

By | 2012 年 10 月 28 日

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;
}
};
```

## 12 thoughts on “LeetCode题目：Substring with Concatenation of All Words”

1. woodpig

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

”for(int i = 0; i <= (int)S.size()-N*M; ++i) “
这里的S.size()前为何要加int？

1. uniEagle Post author

这段代码是copy过来的，感觉上是为了关掉编辑器的警告，因为size()返回的不是int类型。

1. Littlefucker

不是你不改成int 会死循环的。。。因为S.size()返回的是个unsigned

3. cong

偶然看到你的blog，内容很丰富，受益匪浅，不过这篇文章中介绍的方法太慢了. 我想了一种方法，假设word的长度是k，可以将S切成以k为单位长度的段, 例如”barfoothefoobarman”, [“foo”,”bar”], 第一次从第0个开始bar foo the foo bar man, 第二次从第1个字符开始arf oot hef oob arm, 第三次rfo oth efo oba rma, 这样只需要k次循环. 我试过了，只需152ms, 比文章中每个字符挨个循环的方法快了10x. 时间复杂度就省去了，很容易算. 欢迎交流，呵呵

1. uniEagle Post author

额~~现在这个代码是按照你算法中的切割成长度为k的子串进行匹配的啊，你的算法快在哪儿呢？

2. li

我不是很理解你的算法为什么会快这么多。 我理解的你的算法是假设word的长度是k， i是当前搜索的位置， 最外层的loop是从0 -》k – 1, 每一层搜索的位置是
0: 0, k, 2k, 3k …
1: 1, k+1, 2k+1, 3k+1…
2: 2, k+2, 2k+2, …

在我看来这样和所有的位置都搜索是一样的…
请问能具体说明一下或者介意分享一下code吗？

1. fredfsh

他的意思是，复杂度为O(len(S) * k)，每一层只搜一遍就行了