| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
Hard |
|
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"andtarget = "abcba", thensis"?????"initially. In one turn you can:<ul> <li>place <code>stamp</code> at index <code>0</code> of <code>s</code> to obtain <code>"abc??"</code>,</li> <li>place <code>stamp</code> at index <code>1</code> of <code>s</code> to obtain <code>"?abc?"</code>, or</li> <li>place <code>stamp</code> at index <code>2</code> of <code>s</code> to obtain <code>"??abc"</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>
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 <= 1000stampandtargetconsist of lowercase English letters.
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
Let's denote the length of the stamp as
Firstly, we clarify that each starting position corresponds to a window of length
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
After the topological sorting is over, if every position of the target string
The time complexity is
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()
}
}
}