30. Substring with Concatenation of All Words
滑动窗口
初次尝试失败，会超时，213/230，准备看源码
class Solution {
private:
bool mapEqual(map<string, int> mp1, map<string, int> mp2){
map<string, int>::iterator iter1, iter2;
for(iter1 = mp1.begin(); iter1 != mp1.end(); iter1++){
iter2 = mp2.find(iter1->first);
if(iter2 == mp2.end() || iter2->second != iter1->second){
return false;
}
}
return true;
}
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(s.size() == 0 || words.size() == 0){
return res;
}
int wordLen = words[0].size();
int windowsLen = words[0].size() * words.size();
map<string, int> wordMap;
map<string, int>::iterator iter;
for(int i = 0; i < words.size(); i++){
iter = wordMap.find(words[i]);
if(iter == wordMap.end()){
wordMap.insert(pair<string, int>(words[i], 1));
}
else{
iter->second++;
}
}
for(int i = 0; i + windowsLen - 1 < s.size(); i++){
string sub = s.substr(i, windowsLen);
map<string, int> windowMap;
map<string, int>::iterator iter2;
for(int j = 0; j < sub.size(); j+=wordLen){
string word = sub.substr(j, wordLen);
iter2 = windowMap.find(word);
if(iter2 == windowMap.end()){
windowMap.insert(pair<string, int>(word, 1));
}
else{
iter2->second++;
}
}
// wordMap 和 windowMap 比较
bool eql = mapEqual(windowMap, wordMap);
if(eql){
res.push_back(i);
}
}
return res;
}
};
再次查看参考代码，原来对滑动窗口的理解有误，重新写
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if(s.size() == 0 || words.size() == 0){
return res;
}
int wordLen = words[0].size();
int wordNum = words.size();
int windowsLen = words[0].size() * words.size();
map<string, int> wordMap;
map<string, int>::iterator iter;
// 初始化 wordMap
for(int i = 0; i < words.size(); i++){
iter = wordMap.find(words[i]);
if(iter == wordMap.end()){
wordMap.insert(pair<string, int>(words[i], 1));
}
else{
iter->second++;
}
}
// 滑动窗口，累积 wordLen 次
for(int t = 0; t < wordLen; t++){
map<string, int> windowMap;
map<string, int>::iterator iter2, tmp;
int left = t, right = t, cnt = 0;
while(right + wordLen <= s.size()){
// 取出右端进入的 Word, 判断其是否在 Words 中
string w = s.substr(right, wordLen);
right += wordLen;
iter = wordMap.find(w);
if(iter == wordMap.end()){
// 不在，当前滑动窗口无效，移动左端
left = right;
cnt = 0;
windowMap.clear();
}
else{
// 在，将 windowMap 的对应数量+1
iter2 = windowMap.find(w);
if(iter2 == windowMap.end()){
windowMap.insert(pair<string, int>(w, 1));
iter2 = windowMap.find(w);
}
else{
iter2->second++;
}
cnt++;
// 判断是否超数，若超了，从滑动左端依次右移取词并减少其数量，直到满足不超数
while(iter2->second > iter->second){
string tmpStr = s.substr(left, wordLen);
left += wordLen;
tmp = windowMap.find(tmpStr);
if(tmp != windowMap.end()){
tmp->second--;
}
cnt--;
//iter2 = windowMap.find(w);
}
// 若 cnt 相等，则当前滑动窗口满足
if(cnt == wordNum){
res.push_back(left);
}
}
}
}
return res;
}
};