LeetCode 솔루션

[8/21] 936. Stamping The Sequence

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.08.20 22:40

6,860 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

Hard

738139Add to ListShare

You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.

In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp.

For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:
- place stamp at index 0 of s to obtain "abc??",
- place stamp at index 1 of s to obtain "?abc?", or
- place stamp at index 2 of s to obtain "??abc".
Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).

We want to convert s to target using at most 10 * target.length turns.

Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.

Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]
Explanation: Initially s = "?????".
- Place stamp at index 0 to get "abc??".
- Place stamp at index 2 to get "ababc".
[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]
Explanation: Initially s = "???????".
- Place stamp at index 3 to get "???abca".
- Place stamp at index 0 to get "abcabca".
- Place stamp at index 1 to get "aabcaca".

Constraints:

1 <= stamp.length <= target.length <= 1000
stamp and target consist of lowercase English letters.

Accepted

29,418

Submissions

51,998

링크

https://leetcode.com/problems/stamping-the-sequence/ 1625 회 연결

익명
작성일 2022.08.21 13:02

Runtime: 81 ms, faster than 97.01% of Python3 online submissions for Stamping The Sequence.
Memory Usage: 15.4 MB, less than 37.31% of Python3 online submissions for Stamping The Sequence.

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        res = []
        
        combs = set()
        for i in range(len(stamp)):
            for j in range(len(stamp)-i):
                combs.add('#'*i + stamp[i:len(stamp)-j] + '#'*j)
        
        # print(combs)
        
        finished = '#'*len(target)
        
        while target!=finished:
            
            found = False
            
            for i in range(len(target)-len(stamp),-1,-1):
                if target[i:i+len(stamp)] in combs:
                    target = target[:i] + '#'*len(stamp) + target[i+len(stamp):]
                    res.append(i)
                    found = True
            if not found: return []
        
        return res[::-1]