refactor 936

fishercoder1534 · fishercoder1534 · commit b4af8e7f4d4d · 2021-03-31T07:57:33.000-07:00
diff --git a/README.md b/README.md
@@ -395,6 +395,7 @@ _If you like this project, please leave me a star._ &#9733;
 |941|[Valid Mountain Array](https://leetcode.com/problems/valid-mountain-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_941.java) | |Easy|
 |938|[Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_938.java) | |Medium| BST, recursion, DFS
 |937|[Reorder Log Files](https://leetcode.com/problems/reorder-log-files/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_937.java) | |Easy|
+|936|[Stamping The Sequence](https://leetcode.com/problems/stamping-the-sequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_936.java) | |Hard| String, Greedy
 |935|[Knight Dialer](https://leetcode.com/problems/knight-dialer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_935.java) | |Medium|
 |933|[Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_933.java) | |Easy|
 |931|[Minimum Falling Path Sum](https://leetcode.com/problems/minimum-falling-path-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_931.java) | |Medium|Dynamic Programming
diff --git a/src/main/java/com/fishercoder/solutions/_936.java b/src/main/java/com/fishercoder/solutions/_936.java
@@ -0,0 +1,64 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class _936 {
+    public static class Solution1 {
+        /**
+         * credit: https://leetcode.com/problems/stamping-the-sequence/discuss/201546/12ms-Java-Solution-Beats-100
+         * <p>
+         * Think reversely!
+         * How to change target to ****?!
+         */
+        public int[] movesToStamp(String stamp, String target) {
+            List<Integer> moves = new ArrayList<>();
+            char[] s = stamp.toCharArray();
+            char[] t = target.toCharArray();
+            int stars = 0;
+            boolean[] visited = new boolean[target.length()];
+            while (stars < target.length()) {
+                boolean doneReplace = false;
+                for (int i = 0; i <= target.length() - stamp.length(); i++) {
+                    if (!visited[i] && canReplace(t, i, s)) {
+                        stars = doReplace(t, i, s, stars);
+                        doneReplace = true;
+                        visited[i] = true;
+                        moves.add(i);
+                        if (stars == t.length) {
+                            break;
+                        }
+                    }
+                }
+                if (!doneReplace) {
+                    return new int[0];
+                }
+            }
+
+            int[] result = new int[moves.size()];
+            for (int i = 0; i < moves.size(); i++) {
+                result[i] = moves.get(moves.size() - i - 1);
+            }
+            return result;
+        }
+
+        private boolean canReplace(char[] t, int i, char[] s) {
+            for (int j = 0; j < s.length; j++) {
+                if (t[i + j] != '*' && t[i + j] != s[j]) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        private int doReplace(char[] t, int i, char[] s, int stars) {
+            for (int j = 0; j < s.length; j++) {
+                if (t[i + j] != '*') {
+                    t[i + j] = '*';
+                    stars++;
+                }
+            }
+            return stars;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_936Test.java b/src/test/java/com/fishercoder/_936Test.java
@@ -0,0 +1,21 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._936;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _936Test {
+    private static _936.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _936.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertArrayEquals(new int[]{0, 2}, solution1.movesToStamp("abc", "ababc"));
+    }
+}
