Stamping The Sequence

Problem Id: 936 Difficulty: Hard


Intuition

Solution


class Solution:
    def match(self, current, stamp, i):
        for j in range(len(stamp)):
            if current[i + j] == '?' or current[i + j] == stamp[j]:
                continue
            else:
                return False
        return True

    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        used = [False] * (len(target) - len(stamp) + 1)
        current = list(target)
        ans = []
        while current.count('?') != len(current):
            last = used.count(True)
            for i in range(len(target) - len(stamp) + 1):
                if used[i]:
                    continue
                if self.match(current, stamp, i):
                    used[i] = True
                    flag = False
                    for j in range(len(stamp)):
                        if current[i + j] != '?':
                            flag = True
                        current[i + j] = '?'
                    if flag:
                        ans.append(i)
            if used.count(True) == last:
                return []
        return ans[::-1]