陳述：
給定一個字串陣列 S。你可以通過組合陣列 S 中的元素來創建一個字串（你可以多次使用一個元素）
在某些情況下，有很多方法可以從陣列 S 中生成某個字串。
例子：
S = {a, ab, ba}
那么有兩種方法可以使字串“aba”：
- “一個” “巴”
- "ab" "a"
題：
給定一個字串 S 的陣列。找到最短的字串，以便有更多的方法可以從 S 生成該字串。如果沒有，則列印出 -1。
P/S：我想了很多天，但這是迄今為止我得到的最好的一個：
- 生成陣列的所有排列
- 對于每個排列，從陣列 S 中創建一個字串
- 檢查該字串是否是之前創建的，如果是，則列印出該字串，如果不是，則保存該字串。
但是這個演算法顯然不會通過所有的測驗用例。我想不出任何更好的演算法。
uj5u.com熱心網友回復：
這是一個 O(N 3 ) 演算法，其中N是每個字串的總長度：
- 對于 S中的每個元素 S i：
- 為正則運算式 S i (S 1 |...|S n )*構造一個NFA
- 為正則運算式構造一個 NFA (S 1 |...|S i-1 |S i 1 |...|S n )(S 1 |...|S n )*
- 構造一個 NFA，它是步驟 1.1 和步驟 1.2 中的 NFA的交集
- 在步驟 1.3 中找到 NFA 接受的最短字串
- 回傳步驟 1.4 中字串中最短的字串
上述演算法可以改進為O(N 2 logN)：
- 為正則運算式構造一個 NFA (S 1 |...|S n )*
- 在步驟 1 中構建 NFA 的兩個副本的叉積。
- 對于步驟 2 中 NFA 中的每個狀態，從該狀態中找到 NFA 接受的最短字串。
- 讓?? = {S}。
- 雖然??不為空：
- 從 ?? 中取出一個元素 T。
- 將 T 平均分成 P 和 Q。
- 為正則運算式 (P 1 |...|P p )(S 1 |...|S n )*構建 NFA ，重用步驟 1 中的 NFA。
- 為正則運算式 (Q 1 |...|Q q )(S 1 |...|S n )*構建 NFA ，重用步驟 1 中的 NFA。
- 在步驟 3.3 和步驟 3.4 中構建 NFA 的交叉產品，在步驟 2 中重用 NFA。
- 在步驟 3.5 中找到 NFA 接受的最短字串，重用步驟 3 的結果。
- 如果 P 有 1 個以上的元素，則將 P 放入??。
- 如果 Q 有 1 個以上的元素，則將 Q 放入??。
- 回傳步驟 3.6 中字串中最短的字串
uj5u.com熱心網友回復：
在每個有效的解決方案中，我們可以進行兩次切割，其中每個切割的前綴是陣列的一個不同成員（請注意，正下方的 A 和 B 可以具有相同的長度，例如解決方案“a”，給定陣列， ["a", "a"])：
x x x|x x x x x
-A-->|C_0|---->
x x x x x|x x x
----B--->|C_1->
對于每個這樣的組合，A 和 B，可以在一個單詞的長度內遍歷陣列的 trie，我們想要最短的 C 和給定的前綴 C_0，可以通過重復遍歷 trie 獲得。如果 A 和 B 的長度相等，則 C_0 可以為空。如果我們在樹中的每個節點中存盤到葉子的最短距離，一旦我們匹配 C_0，我們就可以用它代替實際的步行來完成 C。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/334522.html