题目链接：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).
这道题的要求是给定字符串S，单词列表L（所有单词均等长），在S中找到包含L中所有单词且只包含一次的子字符串，返回符合该要求的所有子串的首位置。
-
暴力查找
这道题的直接思路是以字符串中每个字符为起始，检查从这个字符开始的子串能否包含L中所有单词且只包含一次。优化查找时，可以对L中的单词进行Hash处理。时间复杂度较高，不过竟然没有超时。。。
时间复杂度：O(nm)（n为字符串S长度，m为单词列表L中单词数量）
空间复杂度：O(ml)（l为单词长度）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution
{
public:
vector<int> findSubstring(string S, vector<string> &L)
{
vector<int> vi;
if(L.size() == 0)
return vi;
for(int i = 0; i + L.size() * L[0].size() - 1 < S.size(); ++ i)
{
unordered_multiset<string> ss(L.cbegin(), L.cend());
for(int j = i; !ss.empty(); j += L[0].size())
{
string str = S.substr(j, L[0].size());
auto iter = ss.find(str);
if(iter == ss.end())
break;
ss.erase(iter);
}
if(ss.empty())
vi.push_back(i);
}
return vi;
}
};
-
双指针查找
可以发现上面的暴力方法中，最坏情况，字符串S中的大部分子串都进行了m次匹配，这其中能否减少次数呢。。。看了该题的Tags或者本文的标签，就回发现这么一个词：Two Point或者双指针。没错，就是这个词，和Longest Substring Without Repeating Characters同样的思路，即使用两个指针维护子串。不同之处是，这道题是判别每个字符串出现过的次数是否超过单词列表中该单词的数量。
思路仍然是维护一个窗口，如果当前单词在单词列表中，则继续移动窗口右端，否则窗口左端可以跳到字符串下一个单词了。
假设字符串S的长度为n，单词列表L中单词的长度为l。因为不是一个字符，所以需要对字符串S所有长度为l的子串进行判断。做法是i从0到l-1个字符开始，得到开始index分别为i, i+l, i+2l, …的长度为l的单词。这样就可以保证判断到所有的满足条件的子串。因为每次扫描的时间复杂度是O(2n/l)（每个单词不会被访问多于两次，一次是窗口右端，一次是窗口左端），总共扫描l次（i=0, …, l-1)，所以总复杂度是O(2n/ll)=O(n)，是一个线性算法。空间复杂度是单词列表的大小，即O(m*l)，其中m是单词列表的单词数量。
思路参考自这里。
时间复杂度：O(n)（n为字符串S长度）
空间复杂度：O(ml)（m为单词列表L中单词数量，l为单词长度）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution
{
public:
vector<int> findSubstring(string S, vector<string> &L)
{
vector<int> vi;
if(L.size() == 0)
return vi;
unordered_map<string, int> msi;
for (int i = 0; i < L.size(); ++ i)
++ msi[L[i]];
for(int i = 0; i < L[0].size(); ++ i)
{
int b = i, cnt = 0;
unordered_map<string, int> tempmsi;
for(int j = i; j + L[0].size() <= S.size(); j += L[0].size())
{
string str = S.substr(j, L[0].size());
if(msi.find(str) != msi.end())
{
++ tempmsi[str];
++ cnt;
if(tempmsi[str] > msi[str])
{
while(tempmsi[str] > msi[str])
{
string s = S.substr(b, L[0].size());
-- tempmsi[s];
-- cnt;
b += L[0].size();
}
}
else if(cnt == L.size())
{
vi.push_back(b);
-- tempmsi[S.substr(b, L[0].size())];
-- cnt;
b += L[0].size();
}
}
else
{
tempmsi.clear();
b = j + L[0].size();
cnt = 0;
}
}
}
return vi;
}
};