LeetCode 936 - Stamping The Sequence

https://leetcode.com/problems/stamping-the-sequence/

You want to form a target string of lowercase letters.

At the beginning, your sequence is target.length '?' marks.  You also have a stamp of lowercase letters.

On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp.  You can make up to 10 * target.length turns.

For example, if the initial sequence is "?????", and your stamp is "abc",  then you may make "abc??", "?abc?", "??abc" in the first turn.  (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)

If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn.  If the sequence is not possible to stamp, return an empty array.

For example, if the sequence is "ababc", and the stamp is "abc", then we could return the answer [0, 2], corresponding to the moves "?????" -> "abc??" -> "ababc".

Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within 10 * target.length moves.  Any answers specifying more than this number of moves will not be accepted.

Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]
([1,0,2] would also be accepted as an answer, as well as some other answers.)

Example 2:

Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]

Note:

1. 1 <= stamp.length <= target.length <= 1000
2. stamp and target only contain lowercase letters

X. Greedy
https://leetcode.com/problems/stamping-the-sequence/discuss/195324/50ms-JAVA-beat-100
https://leetcode.com/problems/stamping-the-sequence/discuss/201546/12ms-Java-Solution-Beats-100

The idea is the same as the most upvoted post. Think reversely!
Let's take an example to illustrate.
Stamp = "abc", Target = "ababcbc`

1. Target = ab***bc
2. Target = ab*****
3. Target = *******

We will go through the whole Target string to find if there exists any substring equals to Stamp. And then replace the whole substring with *. You can see in the step 1, we replace substring abc with ***. Then we keep doing the same thing. In the step 2, you will find we replace substring *bc to ***. * can match to any character because *will be override by the next stamp. Finally we get the result and output the reversed result. When # of stars equals to target.length(), we will return the result. If during one scan, we are not able to replace even one substring with *, directly return empty array.

Comments for two helper functions:
canReplace(char[] T, int p, char[] S) is used to check if any substring from Target is existing to be replaced with *.
doReplace(char[] T, int p, int len, int count) is used to replace the substring with * and return the total number of * we have now.

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        char[] S = stamp.toCharArray();
        char[] T = target.toCharArray();
        List<Integer> res = new ArrayList<>();
        boolean[] visited = new boolean[T.length];
        int stars = 0;
        
        while (stars < T.length) {
            boolean doneReplace = false;
            for (int i = 0; i <= T.length - S.length; i++) {
                if (!visited[i] && canReplace(T, i, S)) {
                    stars = doReplace(T, i, S.length, stars);
                    doneReplace = true;
                    visited[i] = true;
                    res.add(i);
                    if (stars == T.length) {
                        break;
                    }
                }
            }
            
            if (!doneReplace) {
                return new int[0];
            }
        }
        
        int[] resArray = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resArray[i] = res.get(res.size() - i - 1);
        }
        return resArray;
    }
    
    private boolean canReplace(char[] T, int p, char[] S) {
        for (int i = 0; i < S.length; i++) {
            if (T[i + p] != '*' && T[i + p] != S[i]) {
                return false;
            }
        }
        return true;
    }
    
    private int doReplace(char[] T, int p, int len, int count) {
        for (int i = 0; i < len; i++) {
            if (T[i + p] != '*') {
                T[i + p] = '*';
                count++;
            }
        }
        return count;
    } 

https://www.jianshu.com/p/cb4cbd11511b
https://www.acwing.com/solution/leetcode/content/552/
前面所贴的邮票对后面贴的邮票是造成不了影响的
所以反过来思考，将target -> ??????

stamp的长子串是优于stamp的短子串,因为长字串能匹配得到的，那么包含该长字串的子符串一定能匹配得到,而反过来不一定.
举例来说：stamp 为 abcae时, abc能在target匹配得到, 那么ab一定能匹配得到，反过来则不一定
所以枚举stamp的子串, 按照stamp的子串长度从大到小的顺序在target找寻相同的字符串.
因为是要整个stamp一起贴,那么将子串补充为stamp的长度
举例来说：stamp 为 abcae时， abc补充为abc??, ae补充为???ae

在枚举stamp的子串，有可能完整地枚举一次并不能完全的找到,需要多次循环
举例来说
stamp = “uskh”
target = “uskhkhhskh”
完整的枚举一次过程中,得到
????khhskh
??????hskh
???????skh
因为在枚举?skh时, 对应的是target是 ????khhskh,
而在枚举???h后，对应的target是???????skh.

https://github.com/cherryljr/LeetCode/blob/master/Stamping%20The%20Sequence.java

 * Approach: Reverse Simulation
 * 这道题目与 Strange Printer 有点类似，但是本题并不要求最优解。
 * 因此我们可以使用 贪心 的想法去做。
 * 但是这道题目如果按照题目要求的做法 正向（正序） 思考的话，并不能相处什么比较好的做法。
 * 因此我们可以考虑使用逆过来处理的方法来做这道题目。
 * 使用到类似处理方法的还有 Bricks Falling When Hit.
 * 做法为：
 *  因为最后一次的 stamp 必定是会将字符串中的一部分全部改成 stamp.
 *  也就是所谓的 full match.然后将替换的部分全部标记为 '*'.
 *  然后继续进行 match, 但是此时就是 partial match.
 *  并且 '*' 可以与任意字符进行匹配。因为这些字符之后必定会被 stamp 所重新覆写一遍，
 *  所以他们具体是什么并不会造成任何影响。
 *  最后我们只需要将每次得到的结果进行一次 reverse 即可。

    // 因为需要在 doStamp 中对 target 进行修改，所以需要一个成员变量以便访问（Java中字符串类型的限制）
    String myTarget = null;

    public int[] movesToStamp(String stamp, String target) {
        int M = stamp.length(), N = target.length();
        myTarget = target;
        int count = 0;  // 替换的字符个数
        boolean[] visited = new boolean[N];         // 用于记录哪些位置开始的字符被修改过
        List<Integer> index = new ArrayList<>();    // 用于记录每次修改的起始位置
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            sb.append('*');
        }
        // 事先构造出用于替换的字符串
        String replace = sb.toString();

        while (count < N) {
            boolean found = false;
            for (int i = 0; i <= N - M; i++) {
                if (visited[i]) {
                    continue;
                }
                int len = doStamp(stamp, i, replace);
                if (len == 0) {
                    continue;
                }
                visited[i] = true;
                count += len;
                index.add(i);
                found = true;
            }
            if (!found) {
                return new int[]{};
            }
        }

        int size = index.size();
        int[] rst = new int[size--];
        for (int i = 0; i <= size; i++) {
            rst[i] = index.get(size - i);
        }
        return rst;
    }

    // 对从 start 位置开始的字串进行stamp操作，返回替换的字符个数
    // 如果无法匹配的话返回0
    private int doStamp(String stamp, int start, String replace) {
        int changed = stamp.length();
        for (int i = 0; i < stamp.length(); i++) {
            if (myTarget.charAt(start + i) == '*') {
                changed--;
            } else if (myTarget.charAt(start + i) != stamp.charAt(i)) {
                return 0;
            }
        }

        if (changed != 0) {
            myTarget = myTarget.substring(0, start) + replace + myTarget.substring(start + stamp.length());
        }
        return changed;
    }

https://leetcode.com/problems/stamping-the-sequence/discuss/189576/C%2B%2B-simple-greedy

It's better explained through an example. Let's say the target is 'aabccbc', and stamp is 'abc'. We first try to find 'abc' and replace it with '***'. After there are no more replacements, we will try '*bc' and 'ab*', and so on. Now, turn by turn:

'aabccbc' ? 'abc' = [1]
'a***cbc' ? '*bc' = []
'a***cbc' ? 'ab*' = []
'a***cbc' ? 'a**' = [0]
'****cbc' ? '*b*' = []
'****cbc' ? '**c' = [2]
'*****bc' ? '*bc' = [4]

The result is: [4, 2, 0, 1]. It feels to me that this greedy solution produces the minumum possible number of stamps, though I cannot provide a strict proof 

X. https://leetcode.com/problems/stamping-the-sequence/discuss/189258/C%2B%2B-Reverse-Operation-30-ms-better-than-DFS

What I basiclly did here is trying to reverse the whole operations.
The operation token later will be more apperant than the operation token before. The letters which stamped later will cover the letters stamped before and we really don't care about the letters which are covered.

 *  *  *  *  *  *  *
 *  *  * |a  b  c  a|
|a  b  c  a| b  c  a
 a |a  b  c  a| c  a

We just try to match the stamp with the target. Since we do not care about the letters which are coverd by others, so we can apply a * match any letters. For example:

"aabcaca" -> "a****ca" -> "*****ca"->"*******"

It's just my contest code, needed to be revised.

    vector<int> movesToStamp(string stamp, string target) {
        vector<int> ans;
        vector<int> output;
        string str = target;
        string aim(target.length(),'*');
        while(str != aim){
            int tmp = remove(str,stamp);
            if(tmp == str.length()) return output;
            ans.push_back(tmp);
        }
        for(int iter=ans.size()-1;iter>=0;--iter) output.push_back(ans[iter]);
        return output;
    }
    int remove(string& str, string stamp){
        for(int iter=0;iter<str.length();++iter){
            int jter=0,tmp=iter;
            bool flag=false;
            while(jter<stamp.length() && tmp<str.length() && (str[tmp]=='*' || str[tmp]==stamp[jter])){
                if(str[tmp]==stamp[jter]) flag=true;
                tmp++;
                jter++;
            }
            if(jter==stamp.length() && flag){
                for(int kter=0;kter<stamp.length();++kter)
                    str[iter+kter]='*';
                return iter;
            }
        }
        return str.length();
    }

X. DFS
https://leetcode.com/problems/stamping-the-sequence/discuss/189254/Python-Greedy-and-DFS

Another idea is backtracking.

Try to find a path of target,
where path[i] equals to index of target[i] in stamp

Example 1:
Input: stamp = "abc", target = "ababc"
path = [0,1,0,1,2]

Example 2:
Input: stamp = "abca", target = "aabcaca"
path = [0,0,1,2,3,2,3]

The rule is that,
rule 0. path[i + 1] can equal to path[i] + 1
It means target[i] and target[i+1] are on the same stamp.

rule 1. path[i + 1] can equal to 0.
It means t[i + 1] is the start of another stamp

rule 2. if path[i] == stamp.size - 1, we reach the end of a stamp.
Under this stamp, it's another stamp, but not necessary the start.
path[i + 1] can equal to 0 ~ stamp.size - 1.

Step 2:
We need to change path to required moves.

    def movesToStamp(self, s, t):
        if s[0] != t[0] or s[-1] != t[-1]: return []
        n, m = len(s), len(t)
        path = [0] * m
        pos = collections.defaultdict(set)
        for i, c in enumerate(s): pos[c].add(i)

        def dfs(i, index):
            path[i] = index
            if i == m - 1: return index == n - 1
            nxt_index = set()
            if index == n - 1:  # rule 2
                nxt_index |= pos[t[i + 1]]
            elif s[index + 1] == t[i + 1]:  # rule 0
                nxt_index.add(index + 1)
            if s[0] == t[i + 1]:  # rule 1
                nxt_index.add(0)
            return any(dfs(i + 1, j) for j in nxt_index)

        def path2res(path):
            down, up = [], []
            for i in range(len(path)):
                if path[i] == 0:
                    up.append(i)
                elif i and path[i] - 1 != path[i - 1]:
                    down.append(i - path[i])
            return down[::-1] + up

        if not dfs(0, 0): return []
        return path2res(path)

https://leetcode.com/articles/stamping-the-sequence/
Approach 1: Work Backwards

Imagine we stamped the sequence with moves 

$m_1, m_2, \cdots$. Now, from the final position target, we will make those moves in reverse order.

Let's call the ith window, a subarray of target of length stamp.length that starts at i. Each move at position i is possible if the ith window matches the stamp. After, every character in the window becomes a wildcard that can match any character in the stamp.

For example, say we have stamp = "abca" and target = "aabcaca". Working backwards, we will reverse stamp at window 1 to get "a????ca", then reverse stamp at window 3 to get "a??????", and finally reverse stamp at position 0 to get "???????".

Let's keep track of every window. We want to know how many cells initially match the stamp (our "made" list), and which ones don't (our "todo" list). Any windows that are ready (ie. have no todo list), get enqueued.

Specifically, we enqueue the positions of each character. (To save time, we enqueue by character, not by window.) This represents that the character is ready to turn into a "?" in our working target string.

Now, how to process characters in our queue? For each character, let's look at all the windows that intersect it, and update their todo lists. If any todo lists become empty in this manner (window.todo is empty), then we enqueue the characters in window.made that we haven't processed yet.

• Time Complexity: $O(N(N-M))$, where $M, N$ are the lengths of stamp, target.
• Space Complexity: $O(N(N-M))$. 

  public int[] movesToStamp(String stamp, String target) {

    int M = stamp.length(), N = target.length();

    Queue<Integer> queue = new ArrayDeque();

    boolean[] done = new boolean[N];

    Stack<Integer> ans = new Stack();

    List<Node> A = new ArrayList();

    for (int i = 0; i <= N - M; ++i) {

      // For each window [i, i+M), A[i] will contain

      // info on what needs to change before we can

      // reverse stamp at this window.

      Set<Integer> made = new HashSet();

      Set<Integer> todo = new HashSet();

      for (int j = 0; j < M; ++j) {

        if (target.charAt(i + j) == stamp.charAt(j))

          made.add(i + j);

        else

          todo.add(i + j);

      }

      A.add(new Node(made, todo));

      // If we can reverse stamp at i immediately,

      // enqueue letters from this window.

      if (todo.isEmpty()) {

        ans.push(i);

        for (int j = i; j < i + M; ++j)

          if (!done[j]) {

            queue.add(j);

            done[j] = true;

          }

      }

    }

    // For each enqueued letter (position),

    while (!queue.isEmpty()) {

      int i = queue.poll();

      // For each window that is potentially affected,

      // j: start of window

      for (int j = Math.max(0, i - M + 1); j <= Math.min(N - M, i); ++j) {

        if (A.get(j).todo.contains(i)) { // This window is affected

          A.get(j).todo.remove(i);

          if (A.get(j).todo.isEmpty()) {

            ans.push(j);

            for (int m : A.get(j).made)

              if (!done[m]) {

                queue.add(m);

                done[m] = true;

              }

          }

        }

      }

    }

    for (boolean b : done)

      if (!b)

        return new int[0];

    int[] ret = new int[ans.size()];

    int t = 0;

    while (!ans.isEmpty())

      ret[t++] = ans.pop();

    return ret;

  }

}

class Node {

  Set<Integer> made, todo;

  Node(Set<Integer> m, Set<Integer> t) {

    made = m;

    todo = t;

  }

}

http://www.noteanddata.com/leetcode-936-Stamping-The-Sequence-java-solution-note.html

1. 首先，每次转换的时候，可以在任意位置上转换， 如果直接从初始字符串的每个位置全局暴力排列组合，那一定会超时
2. 同时可以想到，如果存在这样一个转换，那么最多在target的每个位置上，都最多只需要stamp一次，
   因为如果在同一个位置上stamp两次的话，前一次操作就白做了，所以没有必要。
   并且如果后一次会在同一个位置上再次stamp的话，前一次操作不会对中间结果产生任何不同的影响
3. 然后可以想到如果从前向后转换的话，会有很多种可能，然后会走到一些fail的case， 需要做backtrack，同时因为状态太多肯定也会超时
   但是如果从后往前转换的话，应该比较固定，
   a. 考虑最后一步转换，因为stamp会被完整的替换上去，所以最后一步的转换一定是在target上找一个子字符串完全和stamp相同来转换，
   否则就不会符合要求。 就想stamp=abc, target=ababc， 最后一步肯定是在尾部stamp一个
   b. 如果target有两个子字符串都是和stamp一样的话，最后一步可以选择两个里面的任何一个，对结果没有影响
   c. 如果最后这一步做了以后， 那么，再往前一步，可以选择其他位置的地方做stamp， 其中，可以覆盖已经stamp过的位置，
   也就是说，倒数第二步如果和最后一步有部分位置重叠的话，也没有关系， 因为倒数第二步的结果会被最后一步覆盖。
   d. 同样，可以依次从后往前不停的找位置做stamp，直到全部字符都被匹配过了，或者是尝试了所有的位置都不能得到可以正确解。
   e. 在从后向前遍历的过程中，为了做到后面的操作可以覆盖前面的操作，可以把每次stamp的字符串变成*,
   这样，前面的stamp操作就是匹配至少一个或多个字符，其他的可以是匹配*， 相当于先stamp一次以后， 后面的stamp可以再上面叠加
   但是每次都至少要匹配一个字符串，否则这个stamp就是一个重复的stamp，没有意义。
   同时，stamp的时候，如果不是*的字符，又必须完全匹配，否则stamp就和结果不一样
   f. 为了减少循环次数，可以利用一个数组保存已经stamp过的位置，也就是应用不能在一个位置上重复stamp的特点