<p>You are given two strings <code>stamp</code> and <code>target</code>. Initially, there is a string <code>s</code> of length <code>target.length</code> with all <code>s[i] == &#39;?&#39;</code>.</p>

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

<ul>
	<li>For example, if <code>stamp = &quot;abc&quot;</code> and <code>target = &quot;abcba&quot;</code>, then <code>s</code> is <code>&quot;?????&quot;</code> initially. In one turn you can:

	<ul>
		<li>place <code>stamp</code> at index <code>0</code> of <code>s</code> to obtain <code>&quot;abc??&quot;</code>,</li>
		<li>place <code>stamp</code> at index <code>1</code> of <code>s</code> to obtain <code>&quot;?abc?&quot;</code>, or</li>
		<li>place <code>stamp</code> at index <code>2</code> of <code>s</code> to obtain <code>&quot;??abc&quot;</code>.</li>
	</ul>
	Note that <code>stamp</code> must be fully contained in the boundaries of <code>s</code> in order to stamp (i.e., you cannot place <code>stamp</code> at index <code>3</code> of <code>s</code>).</li>
</ul>

<p>We want to convert <code>s</code> to <code>target</code> using <strong>at most</strong> <code>10 * target.length</code> turns.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stamp = &quot;abc&quot;, target = &quot;ababc&quot;
<strong>Output:</strong> [0,2]
<strong>Explanation:</strong> Initially s = &quot;?????&quot;.
- Place stamp at index 0 to get &quot;abc??&quot;.
- Place stamp at index 2 to get &quot;ababc&quot;.
[1,0,2] would also be accepted as an answer, as well as some other answers.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stamp = &quot;abca&quot;, target = &quot;aabcaca&quot;
<strong>Output:</strong> [3,0,1]
<strong>Explanation:</strong> Initially s = &quot;???????&quot;.
- Place stamp at index 3 to get &quot;???abca&quot;.
- Place stamp at index 0 to get &quot;abcabca&quot;.
- Place stamp at index 1 to get &quot;aabcaca&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= stamp.length &lt;= target.length &lt;= 1000</code></li>
	<li><code>stamp</code> and <code>target</code> consist of lowercase English letters.</li>
</ul>

class Solution:
    def movesToStamp(self, stamp: str, target: str) -> List[int]:
        # edge case consideration 
        if stamp == target : 
            return [0]

        # get stamp and target length 
        stamp_length, target_length = len(stamp), len(target)
        result = []
        # keep count and max iter for less overhead calculating and processing valuation queries 
        count = 0 
        max_iter = 10*target_length
        # set of permutation covers of the stamp 
        stamp_covers = set()   
        # inner outer loop of stamp_length and stamp_length - outer length 
        # falls in O(stamp_length)^2 and O(stamp_length) 
        # somewhere in that range 
        for outer_index in range(stamp_length):
            for inner_index in range(stamp_length - outer_index):
                # add a stamp cover of # * outer_index + stamp[outer_index to stamp_length - inner_index] + # * inner_index
                # this builds our stamp set over time to include shifting permutations of stamp as our cover 
                stamp_covers.add('#' * outer_index + stamp[outer_index : stamp_length - inner_index] + '#' * inner_index)
		
        # print(s_covers)

		# finish criteria is back to wild card all 
        done = '#' * target_length
		# post fix positioning is of size target_length - s_length 
        post_fix = target_length - stamp_length 
        # ensure post fix is of the appropriate sizing according to problem 
        if post_fix > max_iter : 
            post_fix = max_iter

        # loop in range up to and including post_fix 
        for index in range(post_fix + 1):
            # if target for index to index + stamp length in stamp covers 
            if target[index: index + stamp_length] in stamp_covers :
                # update target, moving backwards towards our goal, by placing the mask on the target 
                target = target[ : index] + '#' * stamp_length + target[index + stamp_length : ] 
                # add the index to the result 
                result.append(index)
                count += 1 

        # if we are done 
        if target == done :
            # if we are within range of solution 
            if count <= max_iter + 1 : 
                return result[ : : -1]
            else : 
                # otherwise, return false 
                return []
        # if we are not done, but are too long already 
        elif count > max_iter + 1 :
            # return false 
            return []

        # loop backwards at this point 
        for index in range(post_fix, -1, -1) :
            # if we have stamp cover, place stamp cover and append index  
            if target[index : index + stamp_length] in stamp_covers:
                target = target[ : index] + '#' * stamp_length + target[index + stamp_length : ]
                result.append(index)
                count += 1 
        
        # if done, check if in bounds and return as appropriate 
        if target == done :
            if count <= max_iter + 1 : 
                return result[ : : -1]
            else : 
                return [] 
        return []
18000