[Leetcode] Substring with Concatenation of All Words

 1 class Solution {
 2 public:
 3     vector<int> findSubstring(string S, vector<string> &L) {
 4         vector<int> res;
 5         if (L.size() < 1) return res;
 6         
 7         int Len = L.size() * L[0].length();
 8         int len = L[0].length();
 9         if (S.length() < Len) return res;
10         
11         map<string, int> word_count;
12         for (int i = 0; i < L.size(); ++i) {
13             word_count[L[i]]++;
14         }
15         map<string, int> word_detect;
16         for (int i = 0; i <= S.length() - Len; ++i) {
17             word_detect.clear();
18             string substr;
19             int j = 0;
20             for (j = 0; j < Len; j += len) {
21                 substr = S.substr(i + j, len);
22                 if (word_count.find(substr) == word_count.end())
23                     break;
24                 ++word_detect[substr];
25                 if (word_detect[substr] > word_count[substr])
26                     break;
27             }
28             if (j==Len) res.push_back(i);
29         }
30         return res;
31     }
32 };