要插入字符串以將其轉換爲迴文的最少字符數

Question

我需要查找將字符串轉換爲迴文所需的最少插入次數。注意：插入可以發生在任何地方，最終或內部。如果只是在最後，我們有一個問題here。

於是我發現，這可以在O(N**2)時間這個簡單的技巧來實現：

1. 讓字符串S1。反轉它。讓它成爲s2。說長度是l。
2. 現在找到s1和s2中最長的公共子序列。讓它的長度爲x。
3. 答案是l-x。

例如，假設s1 = abcda。因此s2 = adcba。長度是5.最長的公共子序列是aba長度爲3.因此最小插入次數是5-3 = 2，這是實際的答案，並生成字符串 - adcbcda。

但是，我無法理解它背後的邏輯。任何人都可以向我解釋爲什麼它有效嗎？

而且，是否有任何O(N)解決方案可能？

Answer 1

我不知道是否有O(N)解決方案，但通過與相反的比較，您會發現一個迴文序列。然後你有l-x未配對的字母。 （如果你在這個詞的中間有一面鏡子，你可以把一個字母對看作它的反射。例如ab | ba）稍後，通過插入，你可以完成圖片。

現在，首先，我們如何找到兩個字符串共有的（最大）子序列？有尋找它看到在這裏 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

當我們試圖找到S1和S2（S1的反向）之間的最長公共子序列（LCS），我們實際上發現的S1和第一上半年之間LCS的多項式算法半s2，s1的後半部分和s2的後半部分。 假設

S1 = abcddzac

所以S2 = cazddcba。在這裏我們可以看到abcd與cazd（上半場）的比較，加上dzac與dcba（下半場）的比較。我們可以看到，兩個比較都是相同的，除了它們彼此相反，所以它們的連接必須是迴文，所以s1和s2的lcs必須是迴文。

一旦我們有了長度爲4的lcs（ad|da），我們又有4個字母打破了對稱性（b，c，z，c）。然後我們爲每個字母插入一個字母來形成對稱，即迴文。我們設置我們的中間點作爲LCS的中點，並認爲我們打破S1爲兩個從中間點，所以我們有

S1 = a BC d|dža c和我們打破它像一根棍子成兩個從d | d，我們結束了：
džaç
d CB a

現在我們只需LCS的字母之間填充，使他們都是一樣的。在我們的例子步驟如下：

džaÇ
d CB a

džaÇ
d ZCB a

d ZC aÇ
d ZCB a

d ZCB aÇ
d ZCB a

d ZCB aÇ
d ZCB aÇ


現在，我們從同一點別讓它和我們有
Ça BCZ dd ZCB a這是一個迴文。

注意：cddc也是一個ldc，但不會改變步驟的數量。