Chuyển chuỗi thành chuỗi palindrome với chèn tối thiểu

Question

Để tìm số lượng chèn tối thiểu cần thiết để chuyển đổi chuỗi đã cho thành palindrome, tôi tìm chuỗi dài nhất của chuỗi (lcs_string) và ngược lại. Do đó, số lần chèn được thực hiện là độ dài (s) - chiều dài (lcs_string)

Phương pháp nào nên được sử dụng để tìm chuỗi số palindrome tương đương khi biết số lượng chèn được thực hiện?

Ví dụ:

1) azbzczdzez

Số chèn yêu cầu: 5 Palindrome chuỗi: azbzcezdzeczbza

Mặc dù nhiều xâu có thể tồn tại cho chuỗi tương tự nhưng tôi muốn tìm chỉ có một palindrome?

Answer 1

Hãy S[i, j] đại diện cho một tiểu chuỗi chuỗi S bắt đầu từ chỉ số i và kết thúc tại index j (cả bao gồm) và c[i, j] là giải pháp tối ưu cho S[i, j].

Rõ ràng, c[i, j] = 0 if i >= j.

Nói chung, chúng ta có tái phát:

Answer 2

Giải pháp có vẻ là giải pháp lập trình động.

Bạn có thể tìm thấy câu trả lời trong bài viết sau đây: How can I compute the number of characters required to turn a string into a palindrome?

Answer 3

Để xây dựng trên VenomFangs trả lời, có một giải pháp quy hoạch động đơn giản với trang này. Lưu ý rằng tôi giả định rằng hoạt động duy nhất được phép ở đây là chèn các ký tự (không xóa, cập nhật). Gọi S là một chuỗi ký tự n. Các đơn giản chức năng đệ quy P cho điều này là:

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

P [i..j]

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

Nếu bạn muốn giải thích thêm về lý do tại sao điều này là đúng, viết bình luận và tôi muốn vui lòng giải thích (mặc dù nó khá dễ dàng để xem với một chút suy nghĩ). Điều này, bằng cách này, là hoàn toàn trái ngược với chức năng LCS bạn sử dụng, do đó xác nhận rằng giải pháp của bạn là trong thực tế tối ưu. Tất nhiên nó hoàn toàn có thể tôi đã vung, nếu có, ai đó cho tôi biết!

Edit: Để giải thích cho các palindrome bản thân, điều này có thể dễ dàng thực hiện như sau: Như đã trình bày ở trên, P [1..n] sẽ cung cấp cho bạn số lượng chèn cần thiết để thực hiện chuỗi này một palindrome. Khi mảng hai chiều ở trên được tạo, đây là cách bạn tìm thấy palindrome:

Bắt đầu với i = 1, j = n. Bây giờ, đầu ra chuỗi = "";

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 

Điều đó có giúp đọc tốt hơn không?

Answer 4

đơn giản.Xem dưới đây :)

 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

PHP Giải pháp của O (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);