936.戳印序列

戳印序列

你想要用小写字母组成一个目标字符串 target。 开始的时候，序列由 target.length 个 ‘?’ 记号组成。 而你有一个小写字母印章 stamp。

在每个回合，你可以将印章放在序列上，并将序列中的每个 ‘?’ 位置替换为印章中的当前字符。

经过若干回合后，最终我们可以得到一些包含 target 的字符串。

返回使用stamp转换target的所需的最少步数。

示例 1:

输入：stamp = “abc”, target = “ababc”
输出：2

示例 2:

输入：stamp = “abca”, target = “aabcaca”
输出：3

提示:

• 1 <= stamp.length <= target.length <= 1000
• stamp 和 target 只包含小写字母

解析

使用逆向思维，从 target 开始反向操作，每次找到一个可以被 stamp 替换的位置，直到所有字符都被确定。

var movesToStamp = function (stamp, target) {
  const m = stamp.length,
    n = target.length;
  const visited = new Array(n).fill(false);
  const result = [];

  const canReplace = (i) => {
    for (let j = 0; j < m; j++) {
      if (target[i + j] !== "?" && target[i + j] !== stamp[j]) return false;
    }
    return true;
  };

  const replace = (i) => {
    let changed = false;
    for (let j = 0; j < m; j++) {
      if (target[i + j] !== "?") changed = true;
      target = target.substring(0, i + j) + "?" + target.substring(i + j + 1);
    }
    return changed;
  };

  let replaced = true;
  while (replaced) {
    replaced = false;
    for (let i = 0; i <= n - m; i++) {
      if (!visited[i] && canReplace(i)) {
        visited[i] = true;
        result.push(i);
        replace(i);
        replaced = true;
      }
    }
  }

  return result.reverse();
};

时间复杂度 O(n * m)，空间复杂度 O(n)。