主題
題目連結：
題目意譯：
給定一個字串陣列 words，回傳最小的字串其包含著 words 中的所有字串作為它的子字串。如果有多個最短的合法字串，則回傳任一個。
你可假設 words 中沒有字串為另一字串的子字串。
限制：
1 ≦ words.length ≦ 12
1 ≦ words[i].length ≦ 20
words[i] 由小寫英文字母組成。
words 中所有字串皆相異。
範例測資：
範例 1：
輸入： words = ["alex","loves","leetcode"]
輸出： "alexlovesleetcode"
解釋： "alex" 、 "loves" 、 "leetcode" 的所有排列也會被接受。
範例 2：
輸入： words = ["catg","ctaagt","gcta","ttca","atgcatc"]
輸出： "gctaagttcatgcatc"
解題思維：
本題可以轉成旅行推銷員問題（Travelling Salesman Problem，TSP），儘管看起來似乎沒什麼關係。以下是我們如何轉換：
因為字串數量 N 不多（最多 N = 12 個），所以我們用一個 32 位元整數的最右邊 12 位元充當每個字串的探訪「狀態」。例如："000000001010" 代表著我們已經探訪了第 1 個（0 based，且從右邊往左數）以及第 3 個字串。
（以下稱第 i 個字串為 S[i]）
而每個字串之間有著「距離」，d[i][j] 代表著用 S[i] 當主體試圖蓋住 S[j]。如果 S[i] 蓋住 S[j] 的最左邊 x 個字元，則我們定義其距離值 d[i][j] = S[i] - x。
因此，現在字串便變得像是彼此之間有距離的「城市」。而我們需要從某個城市開始（代表我們以某個字串作為一開始的主體字串）走過其他每一個城市（代表主體字串要與其他的字串融合成一個更大的字串）。因此本題等價於 TSP 。
不過 TSP 有兩種：一種是要經過所有城市並回到起點；另一種則不需回到起點。前者為求漢密頓循環（Hamiltonian Cycle）；後者為漢密頓路徑（Hamiltonian Path）。而本題因為主體字串最後不需再和自己融合一次，所以屬於後者。
而漢密頓路徑可以用以下方式求得：
我們定義 DP[i][j] 、 path[i][j] ，前者代表著探訪狀態為 i 且從 S[j]（我們目前在 S[j]）探訪到「終點」所累積的最小距離和 、 path[i][j] 則是接下來要從 S[j] 走到哪個字串。
因為我們不需要繞回起點字串，所以「終點」即是所有字串都被探訪過的狀態，即 i = (1 << N) - 1 （所以有 N 個 1）。
因此：
DP[(1 << N) - 1][j] = 0, for 0 ≦ j < N
DP[i][j] = min(d[i][k] + DP[i | (1 << k)][k], for 0 ≦ k < N 且 S[k] 沒有被探訪過（即 i & (1 << k) == 0）), otherwise
也就是在已知目前狀態是 i 且目前在 S[j] 的狀況下，試試看探訪哪個字串 S[k] 會使得 D[i][j] 之值最小。
至於 path[i][j] 的維護也與上面相似，其代表著 S[j] 要走到哪個字串才會使得 D[i][j] 之值最小（也就是說 path[i][j] 負責存 S[k] 之 k 值）。
因為所有字串都可能是開頭，所以我們窮舉開頭字串 S[i] ，然後遞迴 DP[1 << i][i] 和 path[1 << i][i]。因此跑完之後，我們得到了從 S[i] 跑到「終點」的最小距離值，並且根據著 path 陣列我們可以得知 S[i] 要走到的字串 S[j] ，也可知道 S[j] 要走到 S[k] ……以此類推。
因此以 S[i] 的最短之 superstring 即為 S[i] 蓋住 S[j] 蓋住 S[k] ……。也就是說其 superstring 為 S[i] + S[j].substr(S[j].size() - d[i][j]) + S[k].substr(S[k].size() - d[j][k]) + ……，其中 s.substr(Q) 代表著捨棄掉最左邊 Q 個字元只留下剩下右邊的 s.size() - Q 個字元。
而窮舉完所有開頭 S[i] 並獲得它們各自的 superstring 後，看哪個最短即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
