javasharper
diff --git a/‎SubstringwithConcatenationofAllWords/SubstringwithConcatenationofAllWords.cpp
Lines changed: 24 additions & 67 deletions b/‎SubstringwithConcatenationofAllWords/SubstringwithConcatenationofAllWords.cpp
Lines changed: 24 additions & 67 deletions
@@ -1,77 +1,34 @@
 class Solution {
 public:
-    // 1612ms
     vector<int> findSubstring(string S, vector<string> &L) {
-        // Start typing your C/C++ solution below
-        // DO NOT write int main() function
-        
-        int M = L.size();
-        int N = L[0].size();
-        
-        vector<int> indices;
-        if (S.size() < M * N) return indices;
-        
-        for (int i = 0; i < M; i++)
-            words_dict[L[i]] += 1;
-            
-        for (int i = 0; i <= S.size() - M*N; i++) {
-            map<string, int> has_found;
-            bool flag = true;
-            for (int j = 0; j < M; j++) {
-                string sub_string = S.substr(i + j * N, N);
-                if (words_dict.find(sub_string) == words_dict.end()) {
-                    flag = false; break;
-                }
-                has_found[sub_string] += 1;
-                if (has_found[sub_string] > words_dict[sub_string]) {
-                    flag = false; break;
-                }
-            }
-            if (flag) indices.push_back(i);
+        vector<int> result;
+        if (L.empty()) {
+            return result;
         }
-        return indices;
-    }
-};
-
-//
-// Solution2 : 1356ms
-//
-class Solution {
-public:
-    vector<int> findSubstring(string S, vector<string> &L) {
-        // Start typing your C/C++ solution below
-        // DO NOT write int main() function
-        
-        int M = L.size();
-        int N = L[0].size();
-        
-        vector<int> indices;
-        if (S.size() < M * N) return indices;
-        
-        map<string, int> words_dict;
-        for (int i = 0; i < M; i++)
-            words_dict[L[i]] += 1;
-            
-        for (int i = 0; i < N; i++) {
-            vector<string> substrings;
-            for (int j = i; j + N <= S.size(); j += N)
-                substrings.push_back(S.substr(j, N));
-            for (int j = 0; j + M <= substrings.size(); j++) {
-                map<string, int> has_found;
-                bool flag = true;
-                for (int k = 0; k < M; k++) {
-                    if (words_dict.find(substrings[j+k]) == words_dict.end()) {
-                        flag = false; break;
+        int n = L.size();
+        int len = L[0].size();
+        map<string, int> hash;
+        for (int i = 0; i < n; i++) {
+            hash[L[i]] += 1;
+        }
+        for (int i = 0; i < len; i++) {
+            vector<string> slices;
+            for (int j = i; j + len <= S.size(); j += len) {
+                slices.push_back(S.substr(j, len));
+            }
+            for (int j = 0; j + n <= slices.size(); j++) {
+                map<string, int> found;
+                for (int k = 0; k < n; k++) {
+                    found[slices[j+k]] += 1;
+                    if (found[slices[j+k]] > hash[slices[j+k]]) {
+                        break;
                     }
-                    has_found[substrings[j+k]] += 1;
-                    if (has_found[substrings[j+k]] > words_dict[substrings[j+k]]) {
-                        flag = false; break;
+                    if (k == n - 1) {
+                        result.push_back(i + j * len);
                     }
                 }
-                if (flag) indices.push_back(i + j * N);
             }
         }
-        return indices;
+        return result;
     }
-};
+};