936. Stamping The Sequence

Description

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.

 

Solutions

Solution: Greedy

• Time complexity: O((n - stamp.length)² * stamp.length)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} stamp
 * @param {string} target
 * @return {number[]}
 */
const movesToStamp = function (stamp, target) {
  const n = target.length;
  const result = [];
  const current = target.split('');
  const visited = new Array(n).fill(false);
  let masks = 0;

  const isCanReplace = start => {
    for (const [index, element] of stamp.entries()) {
      const value = current[index + start];

      if (value === element || value === '?') continue;
      return false;
    }
    return true;
  };

  const replaceToMask = start => {
    let count = 0;

    for (let index = 0; index < stamp.length; index++) {
      if (current[index + start] === '?') continue;
      current[index + start] = '?';
      count += 1;
    }
    return count;
  };

  while (masks < n) {
    let isStamped = false;

    for (let index = 0; index <= n - stamp.length; index++) {
      if (visited[index] || !isCanReplace(index)) continue;
      masks += replaceToMask(index);
      result.push(index);
      visited[index] = true;
      isStamped = true;
    }
    if (!isStamped) return [];
  }
  return masks === n ? result.reverse() : [];
};