Substring with Concatenation of All Words

 1 class Solution {
 2 public:
 3     //first scan the words, and put each word and its occurance time into an map
 4     //then gradually scan the the string, create a new map and compare it with original map
 5     //if equal, push the first index into result vector
 6     vector<int> findSubstring(string s, vector<string>& words) {
 7         vector<int> result;
 8         if(s.empty() || words.empty()) return result;
 9         int wordsNumber = words.size();
10         int wordLen = words[0].size();
11         int allWordsLen = wordsNumber * wordLen;
12         if(s.size() < allWordsLen) return result;
13         
14         unordered_map<string, int> um;
15         for(int i = 0; i < words.size(); i++)
16             um[words[i]]++;
17             
18         for(int i = 0; i < s.size() - allWordsLen + 1; i++){
19             unordered_map<string, int> tempUm;
20             for(int j = 0; j < wordsNumber; j++){
21                 string temp = s.substr(i + j * wordLen, wordLen);
22                 tempUm[temp]++;
23             }
24             if(tempUm == um)
25                 result.push_back(i);
26         }
27         return result;
28     }
29 };

 1 class Solution {
 2 public:
 3     //first scan the words, and put each word and its occurance time into an map
 4     //then gradually scan the the string, create a new map and compare it with original map
 5     //if equal, push the first index into result vector
 6     vector<int> findSubstring(string s, vector<string>& words) {
 7         vector<int> result;
 8         if(s.empty() || words.empty()) return result;
 9         int wordsNumber = words.size();
10         int wordLen = words[0].size();
11         int allWordsLen = wordsNumber * wordLen;
12         if(s.size() < allWordsLen) return result;
13         
14         unordered_map<string, int> um;
15         for(int i = 0; i < words.size(); i++)
16             um[words[i]]++;
17             
18         for(int i = 0; i < s.size() - allWordsLen + 1; i++){
19             //find the first matched word
20             bool found = false;
21             for(int k = 0; k < wordsNumber; k++){
22                 if(s.substr(i, wordLen) == words[k]){
23                     found = true;
24                     break;
25                 }
26             }
27             if(!found) continue;
28             
29             unordered_map<string, int> tempUm;
30             for(int j = 0; j < wordsNumber; j++){
31                 string temp = s.substr(i + j * wordLen, wordLen);
32                 tempUm[temp]++;
33             }
34             if(tempUm == um)
35                 result.push_back(i);
36         }
37         return result;
38     }
39 };