Участник:F.Nikitin/MovesToStamp

Материал из DISCOPAL
Перейти к: навигация, поиск
def is_valid(stamp, target):
    for s, t in zip(stamp, target):
        if s != "?" and s != t:
            return False
    return True
 
class Solution:    
    def movesToStamp(self, stamp, target):
        ans = []
        m, n = len(stamp),len(target)
        msk, fi = "?" * m, "?" * n
        vis = [False] * (n - m + 1)
        while True:
            flag = False
            for i in range(n - m + 1):
                if not vis[i] and is_valid(target[i:i+m], stamp):
                    vis[i] = True
                    ans.append(i)
                    target = target[:i] + msk + target[i+m:]
                    flag = True
                    break
            if target == fi or flag is False: break
        return ans[::-1] if target == fi else []