將字符串轉換爲迴文字符串，最小插入

Question

爲了找到將給定字符串轉換爲迴文所需的最小插入次數，我找到字符串（lcs_string）及其反向的最長公用子序列。因此要插入的數量是長度（s） - 長度（lcs_string）

在知道要插入的數量時應該使用什麼方法來找到等效的迴文串？

例如：

1）azbzczdzez

需要插入數量：5 迴文字符串：azbzcezdzeczbza

儘管多個迴文字符串可能存在相同的字符串，但我只想要查找一個迴文？

Answer 1

讓S[i, j]表示串S的子串從索引i開始並在索引j（包括兩端）和c[i, j]結束是S[i, j]最優解。

顯然，c[i, j] = 0 if i >= j。

一般情況下，我們有復發：

Answer 2

該解決方案看起來是一個動態編程解決方案。

您可以找到答案在下面的帖子：How can I compute the number of characters required to turn a string into a palindrome?

Answer 3

爲了詳細說明VenomFangs回答，有一個簡單的動態規劃解決這一個。請注意，我假設這裏允許的唯一操作是插入字符（不刪除，更新）。設S是一個n個字符的字符串。這個簡單的遞歸函數P是：

= P [i+1 .. j-1], if S[i] = S[j] 

P [i..j]

= min (P[i..j-1], P[i+1..j]) + 1, 

如果您想爲什麼這是真的更多的解釋，發表評論，我會很樂意解釋（雖然很容易看到一點思路）。順便說一句，這與您使用的LCS功能完全相反，因此驗證您的解決方案實際上是最佳的。當然，如果有的話，我完全有可能會貽誤我的注意！

編輯：爲了考慮迴文本身，這可以輕鬆完成如下： 如上所述，P [1..1]會給你做出這個字符串迴文需要插入的數目。一旦建立了上面的二維數組，就可以找到迴文：

以i = 1，j = n開頭。現在， string output =「」;

while(i < j) 
{ 
    if (P[i][j] == P[i+1][j-1]) //this happens if no insertions were made at this point 
    { 
     output = output + S[i]; 
     i++; 
     j--; 
    } 
    else 
    if (P[i][j] == P[i+1][j]) // 
    { 
     output = output + S[i]; 
     i++; 
    } 
    else 
    { 
     output = S[j] + output; 
     j--; 
    } 
} 
cout<<output<<reverse(output); 
//You may have to be careful about odd sized palindromes here, 
// I haven't accounted for that, it just needs one simple check 

這樣做能讓閱讀更好嗎？

Answer 4

簡單。見下面:)

 String pattern = "abcdefghgf"; 
     boolean isPalindrome = false; 
     int i=0,j=pattern.length()-1; 
     int mismatchCounter = 0; 

     while(i<=j) 
     { 
      //reverse matching 
      if(pattern.charAt(i)== pattern.charAt(j)) 
       { 
        i++; j--; 
        isPalindrome = true; 
        continue; 
       } 

      else if(pattern.charAt(i)!= pattern.charAt(j)) 
       { 
        i++; 
        mismatchCounter++; 
       } 


     } 
     System.out.println("The pattern string is :"+pattern); 
     System.out.println("Minimum number of characters required to make this string a palidnrome : "+mismatchCounter); 

Answer 5

的O PHP解決方案（n）的

function insertNode(&$arr, $idx, $val) { 
    $arr = array_merge(array_slice($arr, 0, $idx), array($val), array_slice($arr, $idx)); 
} 
function createPalindrome($arr, $s, $e) { 
    $i = 0; 
    while(true) { 
     if($s >= $e) { 
      break; 
     } else if($arr[$s] == $arr[$e]) { 
      $s++; $e--; // shrink the queue from both sides 
      continue; 
     } else { 
      insertNode($arr, $s, $arr[$e]); 
      $s++; 
     } 
    } 
    echo implode("", $arr); 
} 
$arr = array('b', 'e', 'a', 'a', 'c', 'd', 'a', 'r', 'e'); 
echo createPalindrome ($arr, 0, count ($arr) - 1);