leetcode hard : Stamping The Sequence

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

Stamping The Sequence - LeetCode

 

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        def match(src, target):
            result = False
            for i in range(slen):
                if src[i] == target[i]:
                    result = True
                elif src[i] == '?':
                    continue
                else:
                    result = False
                    break
            return result
        
        slen = len(stamp)
        tlen = len(target)
        
        answer = []
        for _ in range(10 * tlen):
            matchedAny = False
            
            for i in range(tlen - slen + 1):
                if match(target[i : i + slen], stamp):
                    matchedAny = True
                    answer.append(i)
                    target = target[:i] + '?' * slen + target[i + slen:]
                    if target == '?' * tlen:
                        return reversed(answer)
            if not matchedAny:
                return []
            
        return []

마지막에 찍은 stamp 는 다른 글자에 가려지지 않고 온전한 stamp일것이다.

그것부터 시작해서 역순으로 '?'로 변환해나가면서 인덱스리스트를 만든뒤

나중에 뒤집어서 출력해주면 된다.