【leetcode】 Substring with Concatenation of All Words

地址

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

题目

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.

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).

思路

因为所有待匹配字符串都是长度相同,每两个可匹配的字串的起始位置的间隔都是m的正整数数倍(m是待匹配字符串的长度)。所以可以分别考虑匹配起始位置是模m为k的情况。 假设匹配起始位置是模k为0的情况。如果知道每个匹配位置的能匹配哪个字符串或不能匹配任意一个,则这题就是求数列中区间是否包含所以待匹配字符串id。用hash处理每个字符串的匹配问题。 ps:思路不知道如何表达,,,还是看我代码吧

代码

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
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int cnt[10000],ns[10000],n=s.length(),m=words[0].length(),vn=words.size();
string tmp=words[0];
map<string,int>hs;
set<int>st;
for(int i=0;i<words.size();i++)
{
if(hs[words[i]])
ns[hs[words[i]]]++;
else
hs[words[i]]=i+1,ns[i+1]=1;
}
for(int i=0;i<m;i++)
{
vector<int>num;
memset(cnt,0,sizeof cnt);
for(int j=i;j<n&&j+m<=n;j+=m)
{
for(int k=0;k<m;k++)
tmp[k]=s[j+k];
if(hs.find(tmp)!=hs.end())
num.push_back(hs[tmp]);
else
num.push_back(0);
}
for(int p=0,q=0,k=0;p+vn<=num.size();p++)
{
while(q<p+vn)
{
if(num[q]&&(cnt[num[q]]<ns[num[q]]))
k++,cnt[num[q]]++;
else if(num[q])
cnt[num[q]]++;
q++;
}
if(k==vn)
st.insert(p*m+i);
if(num[p]&&cnt[num[p]]<=ns[num[p]])
k--,cnt[num[p]]--;
else if(num[p])
cnt[num[p]]--;
}
}
vector<int>ans;
for(auto it:st)
ans.push_back(it);
return ans;

}
};