30. 串联所有单词的子串

原题链接：30. 串联所有单词的子串

 

solution:

        哈希表+计数

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;    //定义返回值
        unordered_map<string,int> map;
        for(auto &x : words) map[x]++;  //存储words出现的次数

        //n单词长度,m个单词,字符串长度size
        int m = words.size(),n = words[0].size(),size = s.size();
        for(int i = 0;i + m * n <= size;i++) {
            //子串中出现的单词数量不可能超过words中出现的次数
            unordered_map<string,int> tmp;
            int j;
            //枚举m个单词
            for(j = 0;j < m;j++) {
                string str = s.substr(i + j * n,n); //获取子串
                if(!map.count(str)) break;
                tmp[str]++;
                if(tmp[str] > map[str]) break;
            }
            //否则代表拼接成功
            if(j == m) res.push_back(i);               
        }
        return res;
    }
};

        滑动窗口：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;    //定义返回值
        unordered_map<string,int> map;
        for(auto &x : words) map[x]++;

        int m = words.size(),n = words[0].size(),size = s.size();
        //遍历分组
        /*
        假设n = 4,m = 2,size = 16
        i x x x i x x x i x x x i x x x
        x i x x x i x x x i x x x i x x
        x x i x x x i x x x i x x x i x
        x x x i x x x i x x x i x x x i
        分成4组
        */
        for(int i = 0;i < n;i++) {
            unordered_map<string,int> tmp;
            int cnt = 0;    //维护窗口内串联的有效单词数量
            for(int j = i;j + n <= size;j += n) {
                if(j >= i + m * n) {    //滑动窗口,移除窗口内第一个单词
                    string word = s.substr(j - m * n, n);
                    tmp[word]--;
                    if(tmp[word] < map[word]) cnt--;
                }
                string word = s.substr(j, n);
                tmp[word]++;
                if(tmp[word] <= map[word]) cnt++;
                if(cnt == m) res.push_back(j - (m - 1) * n);                    
            }
        }
        return res;
    }
};