2023-06-28：你想要用小寫字母組成一個(gè)目標(biāo)字符串 target。

開始的時(shí)候，序列由 target.length 個(gè) '?' 記號(hào)組成

而你有一個(gè)小寫字母印章 stamp。

在每個(gè)回合，你可以將印章放在序列上，并將序列中的每個(gè)字母替換為印章上的相應(yīng)字母

你最多可以進(jìn)行 10 * target.length 個(gè)回合

舉個(gè)例子，如果初始序列為 "?????"，而你的印章 stamp 是 "abc"

那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"

（請(qǐng)注意，印章必須完全包含在序列的邊界內(nèi)才能蓋下去。）

如果可以印出序列，那么返回一個(gè)數(shù)組，該數(shù)組由每個(gè)回合中被印下的最左邊字母的索引組成

如果不能印出序列，就返回一個(gè)空數(shù)組。

例如，如果序列是 "ababc"，印章是 "abc"

那么我們就可以返回與操作 "?????" -> "abc??" -> "ababc" 相對(duì)應(yīng)的答案 [0, 2]

另外，如果可以印出序列，那么需要保證可以在 10 * target.length 個(gè)回合內(nèi)完成

任何超過此數(shù)字的答案將不被接受。

輸入：stamp = "abc", target = "ababc"。

輸出：[0,2]。

答案2023-06-28：

大體步驟如下：

1.創(chuàng)建變量s和t，分別存儲(chǔ)印章stamp和目標(biāo)字符串target的字節(jié)數(shù)組表示。

2.創(chuàng)建變量m和n，分別存儲(chǔ)印章長度和目標(biāo)字符串長度。

3.創(chuàng)建數(shù)組inDegrees，長度為n-m+1，初始化每個(gè)元素為m。該數(shù)組表示每個(gè)位置需要匹配的印章字符數(shù)量。

4.創(chuàng)建二維數(shù)組graph，長度為n，每個(gè)位置是一個(gè)空的整數(shù)數(shù)組。該數(shù)組表示目標(biāo)字符串每個(gè)位置對(duì)應(yīng)的可能的匹配位置。

5.創(chuàng)建隊(duì)列queue，長度為n-m+1，用于存儲(chǔ)已經(jīng)匹配完所有印章字符的位置。

6.創(chuàng)建變量l和r，分別表示隊(duì)列queue的左右指針，初始時(shí)都為0。

7.遍歷目標(biāo)字符串，從0到n-m，依次處理每個(gè)位置：

7.1.在當(dāng)前位置i，遍歷印章的每個(gè)字符：

7.1.1.若目標(biāo)字符串t的第i+j個(gè)字符與印章字符相等，表示匹配成功，更新inDegrees數(shù)組，將對(duì)應(yīng)位置的值減1。

7.1.1.1.如果經(jīng)過減1操作后，該位置上印章字符匹配數(shù)量變?yōu)?，將該位置加入隊(duì)列queue，并將右指針r向右移動(dòng)。

7.1.2. 若目標(biāo)字符串t的第i+j個(gè)字符與印章字符不相等，表示匹配失敗，將該位置加入graph[i+j]數(shù)組中，表示可以在該位置之后的某個(gè)位置嘗試匹配印章。

8.創(chuàng)建bool類型的數(shù)組visited，長度為n，用于標(biāo)記目標(biāo)字符串的位置是否被訪問過。

9.創(chuàng)建數(shù)組path，長度為n-m+1，用于記錄完成印章替換的順序。

10.創(chuàng)建變量size，初始為0，表示已經(jīng)完成替換的印章的數(shù)量。

11.當(dāng)左指針l小于右指針r時(shí)，執(zhí)行以下循環(huán)：

11.1.取出隊(duì)列queue中的當(dāng)前位置cur，并將左指針l右移。

11.2.將當(dāng)前位置cur加入數(shù)組path中，并增加size的值。

11.3.遍歷印章的每個(gè)字符：

11.3.1.若當(dāng)前位置cur+i未被訪問過，表示可以嘗試在該位置繼續(xù)匹配印章：

11.3.1.1.將該位置標(biāo)記為已訪問visited[cur+i] = true。

11.3.1.2.遍歷當(dāng)前位置cur+i對(duì)應(yīng)的graph數(shù)組中的每個(gè)位置next：

11.3.1.2.1.更新inDegrees數(shù)組，將對(duì)應(yīng)位置的值減1。

11.3.1.2.1.1.如果經(jīng)過減1操作后，該位置上印章字符匹配數(shù)量變?yōu)?，將該位置加入隊(duì)列queue，并將右指針r向右移動(dòng)。

12.檢查完成替換的印章數(shù)量是否等于n-m+1，如果不相等，返回空數(shù)組[]。

13.將數(shù)組path中的元素按照首尾對(duì)稱的順序重新排列，即交換元素path[i]和path[j]，其中i從0遍歷到size-1，j從size-1遍歷到0。

14.返回?cái)?shù)組path作為結(jié)果。

該程序的總時(shí)間復(fù)雜度和總空間復(fù)雜度為：

總時(shí)間復(fù)雜度：O((n - m + 1) * m)，其中n是target字符串的長度，m是stamp字符串的長度。

總空間復(fù)雜度：O(n)，其中n是target字符串的長度。

go完整代碼如下：

package?main

import?(
????"fmt"
)

func?movesToStamp(stamp?string,?target?string)?[]int?{
????s?:=?[]byte(stamp)
????t?:=?[]byte(target)
????m?:=?len(s)
????n?:=?len(t)
????inDegrees?:=?make([]int,?n-m+1)
????for?i?:=?range?inDegrees?{
????????inDegrees[i]?=?m
????}
????graph?:=?make([][]int,?n)
????for?i?:=?range?graph?{
????????graph[i]?=?[]int{}
????}
????queue?:=?make([]int,?n-m+1)
????l,?r?:=?0,?0
????for?i?:=?0;?i?<=?n-m;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????if?t[i+j]?==?s[j]?{
????????????????if?inDegrees[i]--;?inDegrees[i]?==?0?{
????????????????????queue[r]?=?i
????????????????????r++
????????????????}
????????????}?else?{
????????????????graph[i+j]?=?append(graph[i+j],?i)
????????????}
????????}
????}
????visited?:=?make([]bool,?n)
????path?:=?make([]int,?n-m+1)
????size?:=?0
????for?l?<?r?{
????????cur?:=?queue[l]
????????l++
????????path[size]?=?cur
????????size++
????????for?i?:=?0;?i?<?m;?i++?{
????????????if?!visited[cur+i]?{
????????????????visited[cur+i]?=?true
????????????????for?_,?next?:=?range?graph[cur+i]?{
????????????????????if?inDegrees[next]--;?inDegrees[next]?==?0?{
????????????????????????queue[r]?=?next
????????????????????????r++
????????????????????}
????????????????}
????????????}
????????}
????}
????if?size?!=?n-m+1?{
????????return?[]int{}
????}
????for?i,?j?:=?0,?size-1;?i?<?j;?i,?j?=?i+1,?j-1?{
????????path[i],?path[j]?=?path[j],?path[i]
????}
????return?path
}

func?main()?{
????stamp?:=?"abc"
????target?:=?"ababc"
????result?:=?movesToStamp(stamp,?target)
????fmt.Println(result)
}


rust完整代碼如下：

fn?moves_to_stamp(stamp:?String,?target:?String)?->?Vec<i32>?{
????let?s:?Vec<char>?=?stamp.chars().collect();
????let?t:?Vec<char>?=?target.chars().collect();
????let?m?=?s.len();
????let?n?=?t.len();
????let?mut?in_degrees:?Vec<i32>?=?vec![m?as?i32;?n?-?m?+?1];
????let?mut?graph:?Vec<Vec<i32>>?=?vec![Vec::new();?n];
????let?mut?queue:?Vec<i32>?=?vec![0;?n?-?m?+?1];
????let?mut?l?=?0;
????let?mut?r?=?0;

????for?i?in?0..=n?-?m?{
????????for?j?in?0..m?{
????????????if?t[i?+?j]?==?s[j]?{
????????????????if?in_degrees[i]?>?0?{
????????????????????in_degrees[i]?-=?1;
????????????????}

????????????????if?in_degrees[i]?==?0?{
????????????????????queue[r]?=?i?as?i32;
????????????????????r?+=?1;
????????????????}
????????????}?else?{
????????????????graph[i?+?j].push(i?as?i32);
????????????}
????????}
????}

????let?mut?visited:?Vec<bool>?=?vec![false;?n];
????let?mut?path:?Vec<i32>?=?vec![0;?n?-?m?+?1];
????let?mut?size?=?0;

????while?l?<?r?{
????????let?cur?=?queue[l];
????????l?+=?1;
????????path[size]?=?cur;
????????size?+=?1;

????????for?i?in?0..m?{
????????????let?cur_i?=?cur?+?i?as?i32;
????????????if?!visited[cur_i?as?usize]?{
????????????????visited[cur_i?as?usize]?=?true;
????????????????for?&next?in?&graph[cur_i?as?usize]?{
????????????????????if?in_degrees[next?as?usize]?>?0?{
????????????????????????in_degrees[next?as?usize]?-=?1;
????????????????????}

????????????????????if?in_degrees[next?as?usize]?==?0?{
????????????????????????queue[r]?=?next;
????????????????????????r?+=?1;
????????????????????}
????????????????}
????????????}
????????}
????}

????if?size?!=?n?-?m?+?1?{
????????return?Vec::new();
????}

????for?i?in?0..size?/?2?{
????????let?tmp?=?path[i];
????????path[i]?=?path[size?-?1?-?i];
????????path[size?-?1?-?i]?=?tmp;
????}

????path
}

fn?main()?{
????let?stamp?=?String::from("abc");
????let?target?=?String::from("ababc");
????let?result?=?moves_to_stamp(stamp,?target);
????println!("{:?}",?result);
}


c++完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<algorithm>

using?namespace?std;

vector<int>?movesToStamp(string?stamp,?string?target)?{
????int?m?=?stamp.length();
????int?n?=?target.length();
????vector<int>?inDegrees(n?-?m?+?1,?m);
????vector<vector<int>>?graph(n,?vector<int>());
????vector<int>?queue(n?-?m?+?1,?0);
????int?l?=?0,?r?=?0;

????for?(int?i?=?0;?i?<=?n?-?m;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????if?(target[i?+?j]?==?stamp[j])?{
????????????????if?(--inDegrees[i]?==?0)?{
????????????????????queue[r++]?=?i;
????????????????}
????????????}
????????????else?{
????????????????graph[i?+?j].push_back(i);
????????????}
????????}
????}

????vector<bool>?visited(n,?false);
????vector<int>?path(n?-?m?+?1,?0);
????int?size?=?0;

????while?(l?<?r)?{
????????int?cur?=?queue[l++];
????????path[size++]?=?cur;

????????for?(int?i?=?0;?i?<?m;?i++)?{
????????????if?(!visited[cur?+?i])?{
????????????????visited[cur?+?i]?=?true;

????????????????for?(int?next?:?graph[cur?+?i])?{
????????????????????if?(--inDegrees[next]?==?0)?{
????????????????????????queue[r++]?=?next;
????????????????????}
????????????????}
????????????}
????????}
????}

????if?(size?!=?n?-?m?+?1)?{
????????return?vector<int>();
????}

????reverse(path.begin(),?path.begin()?+?size);
????return?path;
}

int?main()?{
????string?stamp?=?"abc";
????string?target?=?"ababc";

????vector<int>?result?=?movesToStamp(stamp,?target);

????cout?<<?"Result:?";
????for?(int?num?:?result)?{
????????cout?<<?num?<<?"?";
????}
????cout?<<?endl;

????return?0;
}