LeetCode Substring with Concatenation of All Words暴力法暴力法更加暴力的方法(二)
set; i < m - len + 1; i += len) {
if (s[i] < 0) {
// recount
begin = i + len;
count = 0;
found.clear();
found.resize(n, 0);
} else {
int id = s[i];
found[id]++;
if (need[id] && found[id] <= need[id])
count++;
if (count == n)
ret.push_back(begin);
// move current window
if ((i - begin) / len + 1 == n) {
id = s[begin];
if (need[id] && found[id] == need[id])
count--;
found[id]--;
begin += len;
}
}
}
}
return ret;
}
};
最后是原始暴力法，很暴力，速度比上面的慢上10多倍，有图：
实际运行也许更加慢，我在自己的电脑上测试一个很大的数据，前面的方法一下出来了，这个原始的暴力法需要等上6到7秒多。不过胜在它的方法很原始很简单，处理的情况也比较简单。不过太慢了，虽然Accepted了，但是感觉还是不实用的。
[cpp]
vector findSubstring(string &S, vector &L)
{
int sLen = S.length();
int lLen = L.size();
if (lLen < 1) return vector();
int len = L[0].length();
vector res;
map LMap;
map countMap;
string index;
for (auto x: L)
LMap[x]++;
for(int i = 0; i <= S.size()-lLen*len; ++i)
{
countMap.clear();
int j = 0;
for(j = 0; j < lLen; ++j)
{
string index = S.substr(i+j*len, len);
if(LMap.find(index) == LMap.end())
break;
++countMap[index];
if(countMap[index] > LMap[index])
break;
}
if(j == lLen) res.push_back(i);
}
return res;
}