0936 added.

liuyubobobo · liuyubobobo · commit 11a07ef15d83 · 2018-11-04T00:13:19.000-07:00
diff --git a/0936-Stamping-The-Sequence/cpp-0936/CMakeLists.txt b/0936-Stamping-The-Sequence/cpp-0936/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(D)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main.cpp)
+add_executable(D ${SOURCE_FILES})
diff --git a/0936-Stamping-The-Sequence/cpp-0936/main.cpp b/0936-Stamping-The-Sequence/cpp-0936/main.cpp
@@ -0,0 +1,85 @@
+/// Source : https://leetcode.com/problems/stamping-the-sequence/
+/// Author : liuyubobobo
+/// Time   : 2018-11-03
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Reverse Simulation
+/// Time Complexity: O(len(target) * len(stamp))
+/// Space Complexity: O(1)
+class Solution {
+public:
+    vector<int> movesToStamp(string stamp, string target) {
+
+        if(target.size() < stamp.size())
+            return {};
+
+        if(target.size() == stamp.size()){
+            if(stamp == target)
+                return {0};
+            return {};
+        }
+
+        vector<int> res;
+        while(!allQ(target, 0, target.size())){
+
+            int pos = possibleStamp(target, stamp);
+            if(pos == -1)
+                return {};
+
+            res.push_back(pos);
+            for(int i = 0; i < stamp.size(); i ++)
+                target[pos + i] = '?';
+        }
+        reverse(res.begin(), res.end());
+        return res;
+    }
+
+private:
+    bool allQ(const string& s, int start, int end){
+        for(int i = start; i < end; i ++)
+            if(s[i] != '?')
+                return false;
+        return true;
+    }
+
+    int possibleStamp(const string& s, const string& stamp){
+
+        for(int i = 0; i <= s.size() - stamp.size(); i ++)
+            if(!allQ(s, i, i + stamp.size()) && ok(s, i, stamp))
+                return i;
+        return -1;
+    }
+
+    bool ok(const string& s, int start, const string& stamp){
+
+        for(int i = 0; i < stamp.size(); i ++)
+            if(s[start + i] != '?' && s[start + i] != stamp[i])
+                return false;
+        return true;
+    }
+};
+
+
+void print_vec(const vector<int>& vec){
+    for(int e: vec)
+        cout << e << " ";
+    cout << endl;
+}
+
+int main() {
+
+    string stamp1 = "abc", target1 = "ababc";
+    print_vec(Solution().movesToStamp(stamp1, target1));
+    // [0, 2]
+
+    string stamp2 = "abca", target2 = "aabcaca";
+    print_vec(Solution().movesToStamp(stamp2, target2));
+    // [3, 0, 1]
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -588,4 +588,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 933 | [Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/) | [solution](https://leetcode.com/problems/number-of-recent-calls/solution/) | [C++](0933-Number-of-Recent-Calls/cpp-0933/) | | |
 | 934 | [Shortest Bridge](https://leetcode.com/problems/shortest-bridge/) | [solution](https://leetcode.com/problems/shortest-bridge/solution/) | [C++](0934-Shortest-Bridge/cpp-0934/) | | |
 | 935 | [Knight Dialer](https://leetcode.com/problems/knight-dialer/) | [solution](https://leetcode.com/problems/knight-dialer/solution/) | [C++](0935-Knight-Dialer/cpp-0935/) | | |
+| 936 | [Stamping The Sequence](https://leetcode.com/problems/stamping-the-sequence/) | [solution](https://leetcode.com/problems/stamping-the-sequence/solution/) | [C++](0936-Stamping-The-Sequence/cpp-0936/) | | |
 | | | | | | |
