暴力bf过的。
使用map来查找当前定长的字符串是否是“需要”[需要找到]的。
class Solution { public: bool *flag; int len; vector<int>result; vector<int>copy; int sum; vector<int> findSubstring(string S, vector<string> &L) { result.clear(); if(L.size() <= 0)return result; map<string,int>mapr; mapr.clear(); vector<vector<int>>rtable; rtable.clear(); len = L[0].size(); map<string,int>::iterator it; for(int i = 0;i < L.size();i++) { it = mapr.find(L[i]); if(it != mapr.end()) { it->second += 1; } else mapr.insert(map<string,bool>::value_type(L[i],1)); } copy.clear(); sum = 0; for(it = mapr.begin();it != mapr.end();it++) { copy.push_back(it->second); sum += it->second; } bfs(mapr,S,0); return result; } private: void bfs(map<string,int>&mapr,string &S,int start) { if(S.length() - start < sum * len)return ; int position; map<string,int>::iterator it; int min = S.length(); for(it = mapr.begin();it != mapr.end();it++) { string item = it->first; if((position = S.find(item,start)) == string::npos)return ; if(position < min) min = position; } int i = 0; int end; if(bfsStep(mapr,min,S,end)) { end = min + 1; result.push_back(min); } end = min + 1; if(end >= S.length())return; return bfs(mapr,S,end); } void resetMapr(map<string,int>&mapr) { int i = 0; map<string,int>::iterator it; for(it = mapr.begin();it != mapr.end();it++) { it->second = copy[i++]; } } bool bfsStep(map<string,int>&mapr,int pos,string &S,int &end) { int count = 0; map<string,int>::iterator it; int i; for(i = pos;i < S.length();i+=len) { it = mapr.find(string(S,i,len)); if(it == mapr.end() || it->second <= 0) { end = i+len; resetMapr(mapr); return false; } it->second--; count++; if(count == sum) { resetMapr(mapr); return true; } } resetMapr(mapr); if(count == sum)return true; end = i; return false; } };