如何將一個字符串轉換爲迴文最少數量的字符串的字符？

Question

假設字符串是「anuja」，輸出應該是2，因爲如果我刪除字符'u'和'n'，給定的字符串變成迴文。因此輸出應該是最小刪除次數。 更多示例：輸入字符串：「ababa」 輸出：0（不需要移除） 輸入字符串：「abcdba」 輸出：1（刪除'c'或'd'） 請解釋算法。

Answer 1

讓dp[i, j] = minimum number of removals needed to convert the substring [i, j] to a palindrome。我們有：

dp[i, i] = 0 for all i (every single character is a palindrome) 

爲了找到dp[i, j]，讓我們考慮一個隨機字符串。我們有兩種可能性：

1. 第一個和最後一個字符相同：a[i] == a[j]。在這種情況下，我們可以將問題簡化爲找到需要刪除的最少字符數，以便使子字符串[i+1, j-1]成爲迴文。

2. 第一個和最後一個字符不相同：a[i] != a[j]。在這種情況下，我們需要刪除其中的一個。我們將刪除那導致我們更好的解決方案。

因此，我們有：

dp[i, j] = dp[i + 1, j - 1]      # if a[i] == a[j] 
      min(dp[i + 1, j], dp[i, j - 1]) + 1 # otherwise 

爲了您的anuja例子。我們會得到：

| 1 2 3 4 5 
------------- 
1 | 0 1 2 2 2 
2 | 0 1 2 3 
3 |  0 1 2 
4 |  0 1 
5 |   0   

注意，矩陣計算先從主對角線，並繼續向上，從而，與對角線平行於主對角線。答案是dp[1, n]。

這與Levenshtein distance類似，但僅考慮清除。

Answer 2

您可以測量從字符串到其反轉的編輯距離（levenshtein距離）（忽略替換）。期望的值將是這個值的一半。

此問題類似於UVA 10739。這是一個example implementation。

示例實現（適用於你的情況），可以是：

string P, Q; 
getline(cin, P); 
Q = string(P.rbegin(), P.rend()); 
int p = P.size(), q = Q.size(); 

for(int i=0; i<=p; i++) { T[i][0] = i; } 
for(int i=0; i<=q; i++) { T[0][i] = i; } 

for(int i=1; i<=p; i++) { 
    for(int j=1; j<=q; j++) { 
     if (P[i-1] == Q[j-1]) 
      T[i][j] = T[i-1][j-1]; 
     else 
      T[i][j] = min(T[i-1][j], T[i][j-1]) + 1; 
    } 
} 

cout << "Case " << tt << ": " << T[p][q]/2 << endl;