936. Stamping The Sequence

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

Python

Find path from reverse order (Failed Try)

• 概念上是反著找回來，找到stamp在target內的位置，視為最後一個蓋下去的章
• 從最後一個章的位置往左右推，每次都試著找出覆蓋最大的章
• 錯在沒考量到有時候章是跳著蓋的，不一定會跟下個章(這個解法出發的方向)有連續或重疊
• 做個紀錄

Test Case	Passed
"abc" "ababc"	Passed
"abca" "aabcaca"	Passed
"oz" "ooozz"	Passed
"de" "ddeddeddee"	Failed

from collections import deque

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        if stamp not in target:
            return []


        current = ['?'] * len(target)

        left = target.index(stamp)
        right = left + len(stamp)

        # The lastest stamp, as beginning
        ans = deque([left])
        self.stamp_on(current, stamp, left)

        # Count of the stampeed actions
        step = 1


        # Find largest sequence to take the stamp in the left
        start = max(0, left-len(stamp))
        end = min(start+len(stamp), left)
        while left > 0:
            if step > 10:
                break
            print("<", (start, end), ''.join(target[start:end]), stamp[:end-start])
            if ''.join(target[start:end]) == stamp[:end-start]:
                ans.appendleft(start)
                self.stamp_on(current, stamp, start)
                left = start
                start = max(0, left-len(stamp))
                end = min(start+len(stamp), left)
                step += 1
            else:
                start += 1


        # Find largest sequence to take the stamp in the right
        end = min(right+len(stamp), len(target))
        start = max(end-len(stamp), right)
        while right < len(target):
            if step > 10:
                break
            print(">", (start, end), ''.join(target[start:end]), stamp[start-end:])
            if ''.join(target[start:end]) == stamp[start-end:]:
                ans.appendleft(end-len(stamp))
                self.stamp_on(current, stamp, end-len(stamp))
                right = end
                end = min(right+len(stamp), len(target))
                start = max(end-len(stamp), right)
                step += 1
            else:
                end -= 1


        return ans

    def stamp_on(self, current, stamp, start):
        end = min(start+len(stamp), len(current))
        for i in range(start, end):
            if current[i] != '?':
                continue
            current[i] = stamp[i-start]
        print("stamp at {}: {}".format(
            start,
            ''.join(current)
        ))

Offical Solution

• Details see: https://leetcode.com/problems/stamping-the-sequence/solution/

class Solution(object):
    def movesToStamp(self, stamp, target):
        M, N = len(stamp), len(target)

        queue = collections.deque()
        done = [False] * N
        ans = []
        A = []
        for i in range(N - M + 1):
            # For each window [i, i+M),
            # A[i] will contain info on what needs to change
            # before we can reverse stamp at i.

            made, todo = set(), set()
            for j, c in enumerate(stamp):
                a = target[i+j]
                if a == c:
                    made.add(i+j)
                else:
                    todo.add(i+j)
            A.append((made, todo))

            # If we can reverse stamp at i immediately,
            # enqueue letters from this window.
            if not todo:
                ans.append(i)
                for j in range(i, i + len(stamp)):
                    if not done[j]:
                        queue.append(j)
                        done[j] = True

        # For each enqueued letter,
        while queue:
            i = queue.popleft()

            # For each window that is potentially affected,
            # j: start of window
            for j in range(max(0, i-M+1), min(N-M, i)+1):
                if i in A[j][1]:  # This window is affected
                    A[j][1].discard(i) # Remove it from todo list of this window
                    if not A[j][1]:  # Todo list of this window is empty
                        ans.append(j)
                        for m in A[j][0]: # For each letter to potentially enqueue,
                            if not done[m]:
                                queue.append(m)
                                done[m] = True

        return ans[::-1] if all(done) else []