花心能改嘛？ (转载)# Stock
a*e
1 楼
我自己做出来的非常慢，别人的好的答案很快，但我觉得逻辑很复杂，请问有相同复杂
度更简洁一点的答案吗？多谢！
我的慢答案，自己觉得更好解释。（按我现在水平，难以想象能把快答案在45分钟内搞
出来）
class Solution {
public:
vector findSubstring(string S, vector &L) {
vector res;
int nl=L.size();
if (nl==0) return res;
int nw=L[0].size(), ns=S.size();
if (nw==0||ns lmap;
for (int i=0; i
lmap[L[i]]++;
}
int j=0;
while(j+nl*nw<=ns)
{
map tm;
int c=0;
while(c
string tmp=S.substr(j+c*nw,nw);
if (lmap.find(tmp)!=lmap.end())
{
tm[tmp]++;
if(tm[tmp]>lmap[tmp])
break;
}
else
break;
c++;
}
if (c==nl)
res.push_back(j);
j++;
}
return res;
}
};
别人的快答案
class Solution {
public:
vector findSubstring(string S, vector &L) {
int ns=S.size(), nL=L.size(), nw=0;
if (nL!=0) nw=L[0].size();
vector res;
if (ns
unordered_map mp;
for (int i=0; i
for (int i=0; i
int left=i;
unordered_map mp2;
int c=0;
for(int j=i; j<=ns-nw; j+=nw)
{
string subs=S.substr(j,nw);
if(mp.find(subs)!=mp.end())
{
mp2[subs]++;
if (mp2[subs]<=mp[subs])
{
c++;
}
else
{
//one more word
while(mp2[subs]>mp[subs])
{
string str1=S.substr(left, nw);
mp2[str1]--;
if (mp2[str1]
}
}
//come to a result
if (c==nL)
{
res.push_back(left);
//advance one word
mp2[S.substr(left,nw)]--;
c--;
left+=nw;
}
}
else
{
mp2.clear();
c=0;
left=j+nw;
}
}
}
return res;
}
};
度更简洁一点的答案吗？多谢！
我的慢答案，自己觉得更好解释。（按我现在水平，难以想象能把快答案在45分钟内搞
出来）
class Solution {
public:
vector
vector
int nl=L.size();
if (nl==0) return res;
int nw=L[0].size(), ns=S.size();
if (nw==0||ns
for (int i=0; i
lmap[L[i]]++;
}
int j=0;
while(j+nl*nw<=ns)
{
map
int c=0;
while(c
string tmp=S.substr(j+c*nw,nw);
if (lmap.find(tmp)!=lmap.end())
{
tm[tmp]++;
if(tm[tmp]>lmap[tmp])
break;
}
else
break;
c++;
}
if (c==nl)
res.push_back(j);
j++;
}
return res;
}
};
别人的快答案
class Solution {
public:
vector
int ns=S.size(), nL=L.size(), nw=0;
if (nL!=0) nw=L[0].size();
vector
if (ns
unordered_map
for (int i=0; i
for (int i=0; i
int left=i;
unordered_map
int c=0;
for(int j=i; j<=ns-nw; j+=nw)
{
string subs=S.substr(j,nw);
if(mp.find(subs)!=mp.end())
{
mp2[subs]++;
if (mp2[subs]<=mp[subs])
{
c++;
}
else
{
//one more word
while(mp2[subs]>mp[subs])
{
string str1=S.substr(left, nw);
mp2[str1]--;
if (mp2[str1]
}
}
//come to a result
if (c==nL)
{
res.push_back(left);
//advance one word
mp2[S.substr(left,nw)]--;
c--;
left+=nw;
}
}
else
{
mp2.clear();
c=0;
left=j+nw;
}
}
}
return res;
}
};
