方法一 Hierholzer’s Algorithm
相關概念：
1 歐拉路徑：在無向圖中，每個邊只經過一次，形成的路徑。在有向圖中，是指每條有向邊只使用一次，形成的路徑。
2 歐拉回路：歐拉路徑是一個環。
3 在無向圖中，存在歐拉路徑的條件是：每個頂點的邊是偶數。或者圖中有兩個是奇數條邊的頂點。
4 在圖中找歐拉回路的算法Hierholzer’s Algorithm。算法描述是：選擇開始頂點v，沿著頂點v的邊一直訪問直到訪問到頂點v。這個訪問是不可能卡在其他節點停止的，因為圖中所有節點的邊是偶數。從一個頂點進去，就要從一個頂點出來，直到頂點v。這個路徑是一個歐拉回路，但可能沒有覆蓋了圖中所有的邊。在前面一個路徑中如果存在節點u，u有鄰邊還沒有訪問，從頂點u繼續訪問得到一個歐拉回路，將該回路接到上之前訪問的路徑后，得到新的訪問路徑。直到所有頂點的邊都訪問完，得到完整的歐拉回路。
這里注意：新的路徑接到前面的路徑不是簡單的放在后面，而是可能插在中間的。具體細節查看《數據結構與算法分析Java語言描述》第2版的第266,267頁。

翻譯到這都題目是這樣的。所有答案的組合數是k^n。那么我們把前n-1個字符串看做是節點，最后一個字符是邊。例如n=2，k=2，所有可能的組合是00,01,10,11。那么可以把0,1看做節點。0節點有兩條邊，分別為0,1，得到組合00,01。

歐拉回路是：從節點0開始，0,1,1,0;
最后答案將節點0補上 :00110。參考官網解決方案一中提出了post-order概念。
自己的思想：用map構建圖，實現Hierholzer’s算法。

DFS
想法：為了符合要求，最后返回的字符串answer應該包含所有可能的組合。可能的組合數應該是k^n。為了讓answer最短，直覺上應該是使得answer的最后n-1個字符可以重用。
例如：n=2，k=2，所有可能的組合是00,01,10,11。answer=(00110)。
DFS的實現是：
目標：找到包含所有組合的最短字符串
創建圖：節點是所有可能的組合，例如：00,01,10,11；邊：如果node1的最后n-1個字符加上[0,k-1]范圍內的任何一個數可以得到node2，則node1和node2之間有條邊。例如 (00)+1=>(01)，則00和01之間有條邊。
轉移：對每一個節點，取最后n-1位，如果能夠有邊，成功轉移到另外一個未被訪問的節點，則繼續DFS。退出條件是：所有的組合都訪問完成。
來自網頁
代碼實現：

方法二：Inverse Burrows-Wheeler Transform
1 Lyndon Word：Lyndon word 是一個非空字符串，在字典順序上，比它的所有旋轉都要（嚴格地）小。
Lyndon word的性質：一個Lyndon word 被分為左右兩部分，左邊的字符串在字典順序上嚴格小于右邊的字符串。w=uv,u<vw=uv,u<v。如果v盡可能的長，則將u，v稱為標準分解（standard factorization）
舉例來講，用{0,1}可以組成的Lyndon word 可能有：0,1,01,001,011,0001,0011,0111…
來自wiki
2 de Bruijn sequences
將長度為n的Lyndon word 按字典順序鏈接起來，形成de Bruijn sequences。這個視頻中有講解。


這兩張圖片來源于視頻中。
3 Inverse Burrows-Wheeler Transform
IBWT算法生成可以形成de Bruijn 序列的Lyndon word。

總結

以上是生活随笔為你收集整理的753 Cracking the Safe的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。