s:
"barfoothefoobarman"
words:
["foo", "bar"]
先弄一個hash表hword
然後把words裡的單詞存進hword中,每個單詞加1,。
然後周遊s
每次都看一下wn*lenw長度内是不是每個單詞都存在即可
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
int i,j,lens,lenw,wn;
vector<int> res;
unordered_map<string,int> hword,nword;
string w;
lens=s.length();
lenw=words[0].length();
wn=words.size();
hword.clear();
for(i=0;i<wn;i++)
hword[words[i]]++;
for(i=0;i<lens-wn*lenw+1;i++)
{
nword.clear();
for(j=0;j<wn;j++)
{
w=s.substr(i+lenw*j,lenw);
if(hword.find(w)==hword.end())
break;
nword[w]++;
if(nword[w]>hword[w])
break;
}
if(j==wn)
res.push_back(i);
}
return res;
}
};