0030 solved.

liuyubobobo · liuyubobobo · commit 177e4e789c5d · 2022-06-22T16:07:18.000-07:00
diff --git a/0001-0500/0030-Substring-with-Concatenation-of-All-Words/cpp-0030/CMakeLists.txt b/0001-0500/0030-Substring-with-Concatenation-of-All-Words/cpp-0030/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0030)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0030 main.cpp)
diff --git a/0001-0500/0030-Substring-with-Concatenation-of-All-Words/cpp-0030/main.cpp b/0001-0500/0030-Substring-with-Concatenation-of-All-Words/cpp-0030/main.cpp
@@ -0,0 +1,81 @@
+/// Source : https://leetcode.com/problems/substring-with-concatenation-of-all-words/
+/// Author : liuyubobobo
+/// Time   : 2022-06-22
+
+#include <iostream>
+#include <vector>
+#include <map>
+
+using namespace std;
+
+
+/// Sliding Window
+/// Time Complexity: O(word_len * |s|)
+/// Space Complexity: O(|s|)
+class Solution {
+public:
+    vector<int> findSubstring(string s, vector<string>& words) {
+
+        int word_len = words[0].size();
+
+        map<string, int> words_f;
+        for(int i = 0; i < words.size(); i ++) words_f[words[i]] ++;
+
+        vector<int> res;
+        for(int start = 0; start < word_len; start ++){
+
+            vector<string> data;
+            for(int i = start; i < s.size(); i += word_len)
+                data.push_back(s.substr(i, word_len));
+
+            int ok_cnt = 0, l = 0, r = -1;
+            map<string, int> cur_f;
+            while(l < (int)data.size()){
+                if(r + 1 < (int)data.size() && words_f.count(data[r + 1]) && cur_f[data[r + 1]] + 1 <= words_f[data[r + 1]]){
+                    cur_f[data[r + 1]] ++;
+
+                    if(cur_f[data[r + 1]] == words_f[data[r + 1]]){
+                        ok_cnt ++;
+                        if(ok_cnt == words_f.size())
+                            res.push_back(start + l * word_len);
+                    }
+
+                    r ++;
+                }
+                else{
+
+                    if(words_f.count(data[l])){
+                        cur_f[data[l]] --;
+                        if(cur_f[data[l]] + 1 == words_f[data[l]]) ok_cnt --;
+                    }
+                    l ++;
+                    r = max(r, l - 1);
+                }
+            }
+        }
+
+        return res;
+    }
+};
+
+
+void print_vec(const vector<int>& v){
+    for(int e: v) cout << e << ' '; cout << '\n';
+}
+
+int main() {
+
+    vector<string> words1 = {"foo", "bar"};
+    print_vec(Solution().findSubstring("barfoothefoobarman", words1));
+    // 0 9
+
+    vector<string> words2 = {"word","good","best","word"};
+    print_vec(Solution().findSubstring("wordgoodgoodgoodbestword", words2));
+    // empty
+
+    vector<string> words3 = {"bar","foo","the"};
+    print_vec(Solution().findSubstring("barfoofoobarthefoobarman", words3));
+    // 6 9 12
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -76,7 +76,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 027 | [Remove Element](https://leetcode.com/problems/remove-element/description/) | [solution](https://leetcode.com/problems/remove-element/solution/) | [C++](0001-0500/0027-Remove-Element/cpp-0027/) | | |
 | 028 | [Implement strStr()](https://leetcode.com/problems/implement-strstr/description/) | [无]<br/>[缺：完整BM算法, 其他模式匹配算法] | [C++](0001-0500/0028-Implement-strStr/cpp-0028/) | | |
 | 029 | [Divide Two Integers](https://leetcode.com/problems/divide-two-integers/) | [solution](https://leetcode.com/problems/divide-two-integers/solution/)<br/>[缺：不使用乘法加法除法] | [C++](0001-0500/0029-Divide-Two-Integers/cpp-0029/) | | |
-| | | | | | |
+| 030 | [Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/) | [solution](https://leetcode.com/problems/substring-with-concatenation-of-all-words/solution/) | [C++](0001-0500/0030-Substring-with-Concatenation-of-All-Words/cpp-0030/) | | |
 | 031 | [Next Permutation](https://leetcode.com/problems/next-permutation/) | [solution](https://leetcode.com/problems/next-permutation/solution/) | [C++](0001-0500/0031-Next-Permutation/cpp-0031/) | | |
 | | | | | | |
 | 033 | [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/description/) | [solution](https://leetcode.com/problems/search-in-rotated-sorted-array/solution/) | [C++](0001-0500/0033-Search-in-Rotated-Sorted-Array/cpp-0033/) | | |
