本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會(huì)講解多種解題思路及其優(yōu)化，還會(huì)用多種編程語言實(shí)現(xiàn)題解，涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運(yùn)行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動(dòng)，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

有一個(gè)需要密碼才能打開的保險(xiǎn)箱。密碼是?n?位數(shù), 密碼的每一位都是范圍?[0, k - 1]?中的一個(gè)數(shù)字。

保險(xiǎn)箱有一種特殊的密碼校驗(yàn)方法，你可以隨意輸入密碼序列，保險(xiǎn)箱會(huì)自動(dòng)記住?最后?n?位輸入?，如果匹配，則能夠打開保險(xiǎn)箱。

• 例如，正確的密碼是?"345"?，并且你輸入的是?"012345"?：
  • 輸入?0?之后，最后?3?位輸入是?"0"?，不正確。
  • 輸入?1?之后，最后?3?位輸入是?"01"?，不正確。
  • 輸入?2?之后，最后?3?位輸入是?"012"?，不正確。
  • 輸入?3?之后，最后?3?位輸入是?"123"?，不正確。
  • 輸入?4?之后，最后?3?位輸入是?"234"?，不正確。
  • 輸入?5?之后，最后?3?位輸入是?"345"?，正確，打開保險(xiǎn)箱。

在只知道密碼位數(shù)?n?和范圍邊界?k?的前提下，請你找出并返回確保在輸入的?某個(gè)時(shí)刻?能夠打開保險(xiǎn)箱的任一?最短?密碼序列 。

示例 1：

輸入：n = 1, k = 2
輸出："10"
解釋：密碼只有 1 位，所以輸入每一位就可以。"01" 也能夠確保打開保險(xiǎn)箱。

示例 2：

輸入：n = 2, k = 2
輸出："01100"
解釋：對于每種可能的密碼：
- "00" 從第 4 位開始輸入。
- "01" 從第 1 位開始輸入。
- "10" 從第 3 位開始輸入。
- "11" 從第 2 位開始輸入。
因此 "01100" 可以確保打開保險(xiǎn)箱。"01100"、"10011" 和 "11001" 也可以確保打開保險(xiǎn)箱。

提示：

• 1 <= n <= 4
• 1 <= k <= 10
• 1 <= k^n <= 4096

---

保險(xiǎn)箱的密碼是一個(gè)長度為?$n$?的數(shù)字字符串，密碼中每位數(shù)字的取值范圍是從?$0$?到?$k?1$ 。現(xiàn)在這?$n$?位密碼未知，題目要求我們生成一個(gè)可以暴力破解這?$n$?位密碼的字符串序列?$seq$ ，要想用?$seq$?破解密碼，那么?$seq$?中必須包含?$n$?位密碼的所有組合，最簡單的是將?$n$ 位密碼的?$k^n$?個(gè)組合拼在一起構(gòu)成?$seq$ ，但這樣的?$seq$?太長了，題目要我們生成一個(gè)包含?$n$?位密碼所有組合情況的一個(gè)最短序列。

舉個(gè)例子，$n=2,k=2$ ，密碼長度為?$2$ ，每位數(shù)字由 $0$?和?$1$?組成，那么長度為?$2$?的密碼就有?$k^n=2^2=4$?種組合，即?$00,01,10,11$ ，要想破解密碼，最簡做法是，將這四種密碼組合拼在一起組成破解序列?$seq=00011011$ ，這樣得到的序列長度為?$8$ ，但它不是包含所有密碼組合的最短序列。也就是說這種簡單拼接在一起的方法，得到的破解序列是冗余的，會(huì)增加破解時(shí)間。

而密碼破解的方法其實(shí)就是樸素的字符串匹配，比如上面的?$seq=00011011$ ，依次匹配的子串是?$00,00,01,11,10,01,11$ ，一共做了?$7$?次密碼匹配，其中?$00,01,11$?分別匹配了兩次，也就是說多做了?$3$?次冗余的密碼匹配。題目要求的?最短破解序列 就是不會(huì)產(chǎn)生冗余密碼匹配的序列，長度正好是?$k^n+(n?1)$ ，最多只需要匹配?$k^n$?次，$seq=00110$?是上面的其中一個(gè)破解序列，長度為?$5$ ，依次匹配的子串分別是?$00,01,11,10$ ，匹配的正好是所有四種密碼組合。

一種建模方式是：對于所有?$m=k^n$?個(gè)密碼組合，我們把每個(gè)?$n$ 位可能的密碼看成是圖中的一個(gè)頂點(diǎn)，對于這?$m$?個(gè)頂點(diǎn)構(gòu)成的 完全圖?中，讓我們找到這樣一個(gè)回路?$v_1\to v_2\to v_3\to ...\to v_m\to v_1$ ，除起始頂點(diǎn)外每個(gè)頂點(diǎn)訪問且僅訪問一次，其中?$<u,v>$?表示回路中一條由頂點(diǎn) $u$?指向?$v$ 的邊，且頂點(diǎn)?$u$?長為?$n?1$?的后綴恰好是頂點(diǎn)?$v$?的前綴。最終我們要的 最短破解序列 ，一種頂點(diǎn)序列是?$v_1,v_2,v_3,...,v_m$ ，長度為?$k^n+(n?1)$ ，這個(gè)?最短破解序列 不止一個(gè)，因?yàn)?回路?中的任意一個(gè)頂點(diǎn)都可以做?起始頂點(diǎn)。這就是?哈密頓回路問題 。

不過查看Wiki，發(fā)現(xiàn)本題求的答案有專門的術(shù)語 De Bruijn sequence ：$B(k,n)$ 是 $k$ 進(jìn)制元素構(gòu)成的循環(huán)序列，所有長度為 $n$ 的 $k$ 進(jìn)制元素序列都是 $B(k,n)$ 的子數(shù)組（以環(huán)狀形式），在 $B(k,n)$ 中出現(xiàn)且僅出現(xiàn)一次。

描述該循環(huán)序列的圖是 De Bruijn 圖（一張歐拉圖）。使用（$n?1=4?1=3$）3-D De Bruijn 圖可以循環(huán)構(gòu)造長度為 $2^4=16$ 的 B(2,4) De Bruijn 序列。如下的3維 De Bruijn 圖中的每條邊對應(yīng)于一個(gè)四位數(shù)字的序列：三個(gè)數(shù)字分別標(biāo)記該邊要離開的頂點(diǎn)，其后是一個(gè)數(shù)字標(biāo)記該邊。如果一個(gè)人從 $000$ 穿過標(biāo)記為 $1$ 的邊，則一個(gè)人到達(dá) $001$ ，從而表明 De Bruijn 序列中存在子序列 $0001$ 。精確遍歷每條邊一次，就是使用 $16$ 個(gè)四位數(shù)序列中的每一個(gè)恰好一次。下圖，在 B(2,3) 中每個(gè)頂點(diǎn)被訪問一次，而在 B(2,4) 中每條邊（包括自環(huán)）都被遍歷一次。

---

解法 $\text{Hierholzer}$ 算法

$\text{Hierholzer}$ 算法可以在一個(gè)歐拉圖中找出歐拉回路。具體地，我們將所有的 $n?1$ 位數(shù)作為節(jié)點(diǎn)，共有 $k^{n?1}$ 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有 $k$ 條入邊和出邊。如果當(dāng)前節(jié)點(diǎn)對應(yīng)的數(shù)為 $a_1{a}_2?a_{n?1}$ ，那么它的第 $x$ 條出邊就連向數(shù) $a_2?a_{n?1}x$ 對應(yīng)的節(jié)點(diǎn)。這樣從一個(gè)節(jié)點(diǎn)順著第 $x$ 條邊走到另一個(gè)節(jié)點(diǎn)，就相當(dāng)于輸入了數(shù)字 $x$ 。

在某個(gè)節(jié)點(diǎn)對應(yīng)的數(shù)的末尾放上它某條出邊的編號，就形成了一個(gè) $n$ 位數(shù)，并且每個(gè)節(jié)點(diǎn)都能用這樣的方式形成 $k$ 個(gè) $n$ 位數(shù)。

例如 $k=4,n=3$ 時(shí)，節(jié)點(diǎn)分別為 $00,01,02,??,32,33$ ，每個(gè)節(jié)點(diǎn)的出邊的編號分別為 $0,1,2,3$ ，那么 $00$ 和它的出邊形成了 $000,001,002,003$ 這 $4$ 個(gè) $3$ 位數(shù)，$32$ 和它的出邊形成了 $320,321,322,323$ 這 $4$ 個(gè) $3$ 位數(shù)。這樣共計(jì)有 $k^{n?1}\times k=k^n$ 個(gè) $n$ 位數(shù)，恰好就是所有可能的密碼。

由于這個(gè)圖的每個(gè)節(jié)點(diǎn)都有 $k$ 條入邊和出邊（有向連通圖節(jié)點(diǎn)度數(shù)都為 $0$ ），因此它一定存在一個(gè)歐拉回路，即可以從任意一個(gè)節(jié)點(diǎn)開始，一次性不重復(fù)地走完所有的邊且回到該節(jié)點(diǎn)。因此，我們可以用 $\text{Hierholzer}$ 算法找出這條歐拉回路：

• 設(shè)起始節(jié)點(diǎn)對應(yīng)的數(shù)為 $u$ ，歐拉回路中每條邊的編號為 $x_1,x_2,x_3,?$ ，那么最終的字符串即為 $u{x}_1{x}_2{x}_3?u$

$Hierholzer$ 算法如下：

1. 我們從節(jié)點(diǎn) $u$ 開始，任意地經(jīng)過還未經(jīng)過的邊，直到我們「無路可走」。此時(shí)我們一定回到了節(jié)點(diǎn) $u$ ，這是因?yàn)樗泄?jié)點(diǎn)的入度和出度都相等。
2. 回到節(jié)點(diǎn) $u$ 之后，我們得到了一條從 $u$ 開始到 $u$ 結(jié)束的回路，這條回路上仍然有些節(jié)點(diǎn)有未經(jīng)過的出邊。從某個(gè)這樣的節(jié)點(diǎn) $v$ 開始，繼續(xù)得到一條從 $v$ 開始到 $v$ 結(jié)束的回路，再嵌入之前的回路中，即 $$u\to ?\to v\to ?\to u$$
   變?yōu)?$$u\to ?\to v\to ?\to v\to ?\to u$$
3. 以此類推，直到?jīng)]有節(jié)點(diǎn)有未經(jīng)過的出邊，此時(shí)我們就找到了一條歐拉回路。

實(shí)際的代碼編寫具有一定的技巧性。

class Solution {
private:int highest, k;string ans;unordered_set<int> rec;void dfs(int node) {for (int x = 0; x < k; ++x) {int nei = node * 10 + x;if (!rec.count(nei)) { // 改為插入邊rec.insert(nei);dfs(nei % highest);ans += (x + '0');}}}
public:string crackSafe(int n, int k) {this->highest = pow(10, n - 1);this->k = k;dfs(0); // 從n-1個(gè)0出發(fā)ans += string(n - 1, '0'); // 返回的路徑順序應(yīng)該是n-1個(gè)0+翻轉(zhuǎn)的ans// 由于是歐拉回路,所以不用翻轉(zhuǎn),即可直接返回return ans;}
};

但上述寫法比較抽象。我們可以這么寫：從一個(gè) $n?1$ 長度的全 $0$ 串出發(fā)枚舉 $k$ 條邊，每經(jīng)過一條邊就將其加入到哈希表中，防止重復(fù)經(jīng)過同一條邊。

class Solution {
private:string ans;unordered_set<string> edges;void dfs(string &cur, int k) {for (int i = 0; i < k; ++i) {string edge = cur + to_string(i);if (!edges.count(edge)) {edges.insert(edge);string next = edge.substr(1);dfs(next, k);ans += to_string(i);}}}
public:string crackSafe(int n, int k) {string start = string(n - 1, '0');dfs(start, k);ans += start;return ans;}
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n\times k^n)$ 。
• 空間復(fù)雜度：$O(n\times k^n)$ 。