R+没看到要我R+post social media# PDA - 掌中宝
a*e
1 楼
开始写了个brute force的，后来看到下面这个得了31个votes的解法，还有人有更简洁
，更好的解法么？
https://oj.leetcode.com/discuss/366/better-solution-than-brute-force
class Solution {
private:
vector res;
map cntL;
map cn;
int n ;
public:
vector findSubstring(string S, vector &L)
{ res.clear();
cntL.clear();
cn.clear();
n = S.length();
int e = L.size();
int t = L[0].length();
int k = 0;
for(int i = 0; i < e ; i++)
{ if(cn.count(L[i]) == 0)
{ cn[L[i]] = 1;
k++;
}
else
{ cn[L[i]] += 1;
k++;
}
}
string tr ,du;
int r = 0;
int st = 0;
for(int j = 0 ; j < t ; j++)
{ r = 0; st = j;
for(int i = j; i < n; i += t)
{ tr = S.substr(i,t);
if( cn.count(tr) == 0 || cn[tr] == 0 )
{ cntL.clear();
r = 0;
st = i+t;
}
else if(cntL[tr] < cn[tr])
{ cntL[tr] += 1;
r++;
}
else
{ du = S.substr(st,t);
while(du != tr)
{ cntL[du]--;
r--;
st += t;
du = S.substr(st,t);
}
st += t;
}
if(r == k)
{ res.push_back(st);
du = S.substr(st,t);
cntL[du]--;
r--;
st += t;
}
}
cntL.clear();
}
sort(res.begin(),res.end());
return res ;
}
};
，更好的解法么？
https://oj.leetcode.com/discuss/366/better-solution-than-brute-force
class Solution {
private:
vector
map
map
int n ;
public:
vector
{ res.clear();
cntL.clear();
cn.clear();
n = S.length();
int e = L.size();
int t = L[0].length();
int k = 0;
for(int i = 0; i < e ; i++)
{ if(cn.count(L[i]) == 0)
{ cn[L[i]] = 1;
k++;
}
else
{ cn[L[i]] += 1;
k++;
}
}
string tr ,du;
int r = 0;
int st = 0;
for(int j = 0 ; j < t ; j++)
{ r = 0; st = j;
for(int i = j; i < n; i += t)
{ tr = S.substr(i,t);
if( cn.count(tr) == 0 || cn[tr] == 0 )
{ cntL.clear();
r = 0;
st = i+t;
}
else if(cntL[tr] < cn[tr])
{ cntL[tr] += 1;
r++;
}
else
{ du = S.substr(st,t);
while(du != tr)
{ cntL[du]--;
r--;
st += t;
du = S.substr(st,t);
}
st += t;
}
if(r == k)
{ res.push_back(st);
du = S.substr(st,t);
cntL[du]--;
r--;
st += t;
}
}
cntL.clear();
}
sort(res.begin(),res.end());
return res ;
}
};
