Leetcode30：串联所有单词的子串

【题目描述】
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

image.png

【思路】

Solution1

使用两个Hash Map
先将words中的单词映射到map1中
子串长度已知
然后对字符串s进行遍历，对每一个子串进行判断
如何判断呢？
因为单词的长度相同，substr一下 提取出一个单词
然后判断该单词是否在map1中
若不在，该子串不符合要求，下一个子串
若在则map2中数量定为1
若map2中该子串的数量多于map1 --- 不符合要求

何时停止？
记录match 当match的数量等于单词的数量时 将子串开头加入到结果中

【坑】

1. 单词可能有重复的
2. C++里unordermap的使用

unordermap<string,int> map;
cout<<map.size()<<endl; //0
cout<<map["a"]<<endl;  //0
cout<<map.size()<<endl; //1

这里map1的size会随着运行有变化
所以后面判断match的时候 要用一开始的map1.size（）判断

代码记录

vector<int> findSubstring(string s, vector<string>& words) {
    unordered_map<string, int> map1;
    unordered_map<string, int> map2;
    vector<int> res;
    if (words.size() == 0) return res;
    for (int i = 0; i < words.size(); i++) { // build hash map 1
        string st = words[i];
        map1[st]++;
    }

    int word_len = words[0].size();
    int word_num = words.size();
    int map_size = map1.size();

    for (int i = 0; i + word_len * word_num <= s.size(); i++) {
        int match = 0;
        for (int j = i; j < i+word_len * word_num; j = j + word_len) {
            string subS = s.substr(j, word_len); // cut a word
            cout << subS << endl;
            if (map1[subS]== 0) break;// the word not in map1, jump out of loop}
            else {
                map2[subS]++;
                if (map2[subS] == map1[subS]) {
                    match++;
                    cout << "match++: " << match << endl;
                    cout << "map1 size: " << map1.size() << endl;
                    if (match == map_size) {
                        cout << "res push back ！！" << endl;
                        res.push_back(i);
                    }
                }
                else if (map2[subS] > map1[subS]) break; // more words, jump out

                //if (match == map1.size()) res.push_back(i);
            }

        }
        map2.clear();
    
    }
    return res;
}