Question

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 1: Reverse Thinking + Topological Sorting

If we operate on the sequence in a forward manner, it would be quite complicated because subsequent operations would overwrite previous ones. Therefore, we consider operating on the sequence in a reverse manner, i.e., starting from the target string $target$ and considering the process of turning $target$ into $?????$.

Let's denote the length of the stamp as $m$ and the length of the target string as $n$. If we operate on the target string with the stamp, there are $n-m+1$ starting positions where the stamp can be placed. We can enumerate these $n-m+1$ starting positions and use a method similar to topological sorting to operate in reverse.

Firstly, we clarify that each starting position corresponds to a window of length $m$.

Next, we define the following data structures or variables:

• In-degree array $indeg$, where $indeg[i]$ represents how many characters in the $i$-th window are different from the characters in the stamp. Initially, $indeg[i]=m$. If $indeg[i]=0$, it means that all characters in the $i$-th window are the same as those in the stamp, and we can place the stamp in the $i$-th window.
• Adjacency list $g$, where $g[i]$ represents the set of all windows with different characters from the stamp on the $i$-th position of the target string $target$.
• Queue $q$, used to store the numbers of all windows with an in-degree of $0$.
• Array $vis$, used to mark whether each position of the target string $target$ has been covered.
• Array $ans$, used to store the answer.

Then, we perform topological sorting. In each step of the topological sorting, we take out the window number $i$ at the head of the queue, and put $i$ into the answer array $ans$. Then, we enumerate each position $j$ in the stamp. If the $j$-th position in the $i$-th window has not been covered, we cover it and reduce the in-degree of all windows in the $indeg$ array that are the same as the $j$-th position in the $i$-th window by $1$. If the in-degree of a window becomes $0$, we put it into the queue $q$ for processing next time.

After the topological sorting is over, if every position of the target string $target$ has been covered, then the answer array $ans$ stores the answer we are looking for. Otherwise, the target string $target$ cannot be covered, and we return an empty array.

The time complexity is $O(n \times (n - m + 1))$, and the space complexity is $O(n \times (n - m + 1))$. Here, $n$ and $m$ are the lengths of the target string $target$ and the stamp, respectively.

class Solution:
  def movesToStamp(self, stamp: str, target: str) -> List[int]:
    m, n = len(stamp), len(target)
    indeg = [m] * (n - m + 1)
    q = deque()
    g = [[] for _ in range(n)]
    for i in range(n - m + 1):
      for j, c in enumerate(stamp):
        if target[i + j] == c:
          indeg[i] -= 1
          if indeg[i] == 0:
            q.append(i)
        else:
          g[i + j].append(i)
    ans = []
    vis = [False] * n
    while q:
      i = q.popleft()
      ans.append(i)
      for j in range(m):
        if not vis[i + j]:
          vis[i + j] = True
          for k in g[i + j]:
            indeg[k] -= 1
            if indeg[k] == 0:
              q.append(k)
    return ans[::-1] if all(vis) else []

class Solution {
  public int[] movesToStamp(String stamp, String target) {
    int m = stamp.length(), n = target.length();
    int[] indeg = new int[n - m + 1];
    Arrays.fill(indeg, m);
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, i -> new ArrayList<>());
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n - m + 1; ++i) {
      for (int j = 0; j < m; ++j) {
        if (target.charAt(i + j) == stamp.charAt(j)) {
          if (--indeg[i] == 0) {
            q.offer(i);
          }
        } else {
          g[i + j].add(i);
        }
      }
    }
    List<Integer> ans = new ArrayList<>();
    boolean[] vis = new boolean[n];
    while (!q.isEmpty()) {
      int i = q.poll();
      ans.add(i);
      for (int j = 0; j < m; ++j) {
        if (!vis[i + j]) {
          vis[i + j] = true;
          for (int k : g[i + j]) {
            if (--indeg[k] == 0) {
              q.offer(k);
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        return new int[0];
      }
    }
    Collections.reverse(ans);
    return ans.stream().mapToInt(Integer::intValue).toArray();
  }
}

class Solution {
public:
  vector<int> movesToStamp(string stamp, string target) {
    int m = stamp.size(), n = target.size();
    vector<int> indeg(n - m + 1, m);
    vector<int> g[n];
    queue<int> q;
    for (int i = 0; i < n - m + 1; ++i) {
      for (int j = 0; j < m; ++j) {
        if (target[i + j] == stamp[j]) {
          if (--indeg[i] == 0) {
            q.push(i);
          }
        } else {
          g[i + j].push_back(i);
        }
      }
    }
    vector<int> ans;
    vector<bool> vis(n);
    while (q.size()) {
      int i = q.front();
      q.pop();
      ans.push_back(i);
      for (int j = 0; j < m; ++j) {
        if (!vis[i + j]) {
          vis[i + j] = true;
          for (int k : g[i + j]) {
            if (--indeg[k] == 0) {
              q.push(k);
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        return {};
      }
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

func movesToStamp(stamp string, target string) (ans []int) {
  m, n := len(stamp), len(target)
  indeg := make([]int, n-m+1)
  for i := range indeg {
    indeg[i] = m
  }
  g := make([][]int, n)
  q := []int{}
  for i := 0; i < n-m+1; i++ {
    for j := range stamp {
      if target[i+j] == stamp[j] {
        indeg[i]--
        if indeg[i] == 0 {
          q = append(q, i)
        }
      } else {
        g[i+j] = append(g[i+j], i)
      }
    }
  }
  vis := make([]bool, n)
  for len(q) > 0 {
    i := q[0]
    q = q[1:]
    ans = append(ans, i)
    for j := range stamp {
      if !vis[i+j] {
        vis[i+j] = true
        for _, k := range g[i+j] {
          indeg[k]--
          if indeg[k] == 0 {
            q = append(q, k)
          }
        }
      }
    }
  }
  for _, v := range vis {
    if !v {
      return []int{}
    }
  }
  for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    ans[i], ans[j] = ans[j], ans[i]
  }
  return
}

function movesToStamp(stamp: string, target: string): number[] {
  const m: number = stamp.length;
  const n: number = target.length;
  const indeg: number[] = Array(n - m + 1).fill(m);
  const g: number[][] = Array.from({ length: n }, () => []);
  const q: number[] = [];
  for (let i = 0; i < n - m + 1; ++i) {
    for (let j = 0; j < m; ++j) {
      if (target[i + j] === stamp[j]) {
        if (--indeg[i] === 0) {
          q.push(i);
        }
      } else {
        g[i + j].push(i);
      }
    }
  }

  const ans: number[] = [];
  const vis: boolean[] = Array(n).fill(false);
  while (q.length) {
    const i: number = q.shift()!;
    ans.push(i);
    for (let j = 0; j < m; ++j) {
      if (!vis[i + j]) {
        vis[i + j] = true;
        for (const k of g[i + j]) {
          if (--indeg[k] === 0) {
            q.push(k);
          }
        }
      }
    }
  }
  if (!vis.every(v => v)) {
    return [];
  }
  ans.reverse();
  return ans;
}

use std::collections::VecDeque;

impl Solution {
  pub fn moves_to_stamp(stamp: String, target: String) -> Vec<i32> {
    let m = stamp.len();
    let n = target.len();

    let mut indeg: Vec<usize> = vec![m; n - m + 1];
    let mut g: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut q: VecDeque<usize> = VecDeque::new();

    for i in 0..n - m + 1 {
      for j in 0..m {
        if
          target
            .chars()
            .nth(i + j)
            .unwrap() == stamp.chars().nth(j).unwrap()
        {
          indeg[i] -= 1;
          if indeg[i] == 0 {
            q.push_back(i);
          }
        } else {
          g[i + j].push(i);
        }
      }
    }

    let mut ans: Vec<i32> = Vec::new();
    let mut vis: Vec<bool> = vec![false; n];

    while let Some(i) = q.pop_front() {
      ans.push(i as i32);

      for j in 0..m {
        if !vis[i + j] {
          vis[i + j] = true;

          for &k in g[i + j].iter() {
            indeg[k] -= 1;
            if indeg[k] == 0 {
              q.push_back(k);
            }
          }
        }
      }
    }

    if vis.iter().all(|&v| v) {
      ans.reverse();
      ans
    } else {
      Vec::new()
    }
  }
}