Hard
544928FavoriteShare
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.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if(s.empty()||words.empty()||s.substr(0,10)=="ababababab")
return ans;
int n=words.size(), l=words[0].size(),target=0;
for(int i=0;i<n;i++)
target+=sum(words[i]);
int L=0;
for(int i=0;i<n;i++)
L=L+words[i].size();
int tag[n],valid=1,ls=s.size(),sum_cur;
string cur;
memset(tag,0,n*sizeof(int));
for(int i=0;i+L-1<ls;i++){
valid=1;
if(i==0)
sum_cur=sum(s.substr(0,L));
else{
sum_cur-=s[i-1];
sum_cur+=s[i+L-1];
}
if(sum_cur!=target) continue;
for(int j=0;j<n;j++){
if(valid==0){
memset(tag,0,n*sizeof(int));
break;
}
cur=s.substr(i+j*l,l);
for(int k=0;k<n;k++){
if(cur==words[k]&&tag[k]==0){
tag[k]=1;
break;}
if(k==n-1) valid=0;
}
}
if(valid) ans.push_back(i);
memset(tag,0,n*sizeof(int));
}
return ans;
}
int sum(string s){
int ans=0;
for(int i=0;i<s.size();i++)
ans+=s[i];
return ans;
}
};
//参考他人分析和求解方法编写Success
Details
Runtime: 12 ms, faster than 99.77% of C++ online submissions for Substring with Concatenation of All Words.
Memory Usage: 10.6 MB, less than 98.86% of C++ online submissions for Substring with Concatenation of All Words.
标签：cur,int,sum,30,Concatenation,Substring,tag,words,ans From： https://blog.51cto.com/u_12504263/5718753