给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = “barfoothefoobarman”,
words = [“foo”,”bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoor” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = “wordgoodgoodgoodbestword”,
words = [“word”,”good”,”best”,”word”]
输出：[]
解法1：滑动窗口
普通滑动窗口
思路：
- 1.用hashmap将words中的所有单词个数记录
- 2.遍历s字符串，找到符合的连续子串记录起始位置
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
| class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(words.size()<1||s.size()<1||words[0].size()*words.size()>s.size())
return res;
int wordlen=words[0].size();
int len=wordlen*words.size();
unordered_map<string,int> hashmapword;
int i;
for(i=0;i<words.size();i++)
{
hashmapword[words[i]]++;
}
for(i=0;i<s.size()-len+1;i++)
{
unordered_map<string,int> hashmaps(hashmapword);
int j;
for(j=0;j<words.size();j++)
{
string str=s.substr(i+j*words[0].size(),words[0].size());
if(hashmaps[str]==0)
{
hashmaps.clear();
break;
}
hashmaps[str]--;
}
if(j==words.size())
res.push_back(i);
}
return res;
}
};
|
解法2：优化的滑动窗口
我们发现其中有很多不必要的步骤可以简化，
在解法1中我们每次都是移动一个字符，因为每个单词长度相同所有，我们可以每次移动一个单词的长度，将这些移动分为words[i].size()类
我们以从0开始移动为例，开始讨论优化情况
情况一：当子串完全匹配，移动到下一子串的时候。
保存当前匹配情况，只让起始位置的单词变为当前下一位置单词进行判断
情况二：当判断过程中，出现不符合单词
i直接移动当前位置，将当前匹配情况清空
情况三：出现符合的单词，但次数超过。
将当前匹配情况从头开始退出，直到该符合的单词被移除，即当前匹配hashmap中次数与要求次数相等时，即可进行正常判断，i前进单词数*单词长度个单位
注意：我们需要添加一个bool hashRemoved 防止情况3移除后情况1继续移除，我们需要一个新的hashmap保存当前匹配情况
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
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(words.size()<1||s.size()<1||words[0].size()*words.size()>s.size())
return res;
int wordlen=words[0].size();
int len=words.size();
unordered_map<string,int> hashmapword;
int k;
int i;
for(i=0;i<words.size();i++)
{
hashmapword[words[i]]++;
}
for(k=0;k<wordlen;k++)
{
int count=0;
unordered_map<string,int> hashmaps;
for(i=k;i<s.size()-len*wordlen+1;i+=wordlen)
{
bool hashremove=false;
while(count<len)
{
string str=s.substr(i+count*wordlen,wordlen);
if(hashmapword.count(str)!=0)
{
hashmaps[str]++;
if(hashmaps[str]>hashmapword[str])
{
hashremove=true;
int removenum=0;
while(hashmaps[str]>hashmapword[str])
{
string first=s.substr(i+removenum*wordlen,wordlen);
hashmaps[first]--;
removenum++;
}
count=count-removenum+1;
i=i+(removenum-1)*wordlen;
break;
}
}
else
{
hashmaps.clear();
i=i+count*wordlen;
count=0;
break;
}
count++;
}
if(count==words.size())
res.push_back(i);
if(count>0&&(!hashremove))
{
string first=s.substr(i,wordlen);
hashmaps[first]--;
count--;
}
}
}
return res;
}
};
|