30. concatenate substrings of all words

Original link ：30. Concatenate the substrings of all words

 

solution:

        Hashtable + Count

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;    // Define the return value 
        unordered_map<string,int> map;
        for(auto &x : words) map[x]++;  // Storage words Number of occurrences 

        //n Word length ,m Word , String length size
        int m = words.size(),n = words[0].size(),size = s.size();
        for(int i = 0;i + m * n <= size;i++) {
            // The number of words in the substring cannot exceed words Is the number of times 
            unordered_map<string,int> tmp;
            int j;
            // enumeration m Word 
            for(j = 0;j < m;j++) {
                string str = s.substr(i + j * n,n); // Get substring 
                if(!map.count(str)) break;
                tmp[str]++;
                if(tmp[str] > map[str]) break;
            }
            // Otherwise, the splicing is successful 
            if(j == m) res.push_back(i);               
        }
        return res;
    }
};

        The sliding window ：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;    // Define the return value 
        unordered_map<string,int> map;
        for(auto &x : words) map[x]++;

        int m = words.size(),n = words[0].size(),size = s.size();
        // Traversal group 
        /*
         hypothesis 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
         Divide into 4 Group 
        */
        for(int i = 0;i < n;i++) {
            unordered_map<string,int> tmp;
            int cnt = 0;    // Maintain the number of valid words concatenated in the window 
            for(int j = i;j + n <= size;j += n) {
                if(j >= i + m * n) {    // The sliding window , Remove the first word in the window 
                    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;
    }
};