0936._Stamping_The_Sequence.md

936. Stamping The Sequence

难度: Hard

刷题内容

原题连接

• 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 <= stamp.length <= target.length <= 1000
stamp and target only contain lowercase letters.

解题方案

思路 1 - 时间复杂度: O(len(t) * (len(t) - len(s)) * len(t))- 空间复杂度: O(len(t))******

完全可以反向思考，我把盖章一张一张撕下来，按照贴上去的顺序逆序撕

每撕下一张盖章，我就把它所覆盖的位置全部变为'?'

那么如何判断一个盖章是否可以覆盖呢？只要当前范围target[i:i+len(stamp)]能够match我们的stamp就行了

比如

如果target[i:i+len(stamp)] = 'abc???', stamp = 'abcbac'，这样就是可以match的

但是如果target[i:i+len(stamp)] = '??????', stamp = 'abcbac'，这样就不行了，因为我们的target那一块范围之前压根就没有盖章

如果target[i:i+len(stamp)] = 'abc???', stamp = 'bbcbac'，这样也不行，因为字母对不上呀

class Solution:
    def movesToStamp(self, stamp: 'str', target: 'str') -> 'List[int]':
        def match(cur, stamp):
            flag = False # 判定是否全为 '?'，如果是则不能 match
            for c1, c2 in zip(cur, stamp):
                if c1 == '?':
                    continue
                elif c1 != c2:
                    return False
                else:
                    flag = True
            return flag
        res, root, moves = [], '?' * len(target), 0
        while moves < len(target) - len(stamp) + 1: # 最多撕 len(target) - len(stamp) + 1 张邮票
            change = False
            for i in range(len(target) - len(stamp) + 1):
                if match(target[i:], stamp):
                    moves += 1
                    change = True
                    res.append(i)
                    target = target[:i] + '?' * len(stamp) + target[i+len(stamp):]
                if target == root:
                    return res[::-1]
            if not change:
                break
        return []