C++에서 문자열 회문을 만들기 위한 최소 삭제 횟수입니다.

문제 설명

크기가 'n'인 문자열이 주어집니다. 작업은 문자열 회문을 만들기 위해 최소 문자 수를 삭제하는 것입니다.

주어진 문자열이 "abcda"이면 첫 번째와 마지막을 제외한 2개의 문자를 삭제하여 회문으로 만들 수 있습니다.

• 문자 'b'와 'c'를 삭제하면 "ada" 문자열은 회문입니다.

• 문자 'c'와 'd'를 삭제하면 "aba" 문자열은 회문입니다.

• 문자 'b'와 'd'를 삭제하면 "aca" 문자열은 회문입니다

알고리즘

1. Find longest palindromic subsequence of given string. Let’s call it as “lpsSize”.
2. Minimum characters to be deleted = (length of string – lpsSize) Code.

예시

#include <iostream>
#include <algorithm>
using namespace std;
int lps(string s, int i, int j){
   if (i == j) {
      return 1;
   }
   if (s[i] == s[j] && i + 1 == j) {
      return 2;
   }
   if (s[i] == s[j]) {
      return lps(s, i + 1, j - 1) + 2;
   }
   return max(lps(s, i, j - 1), lps(s, i + 1, j));
}
int minDeletion(string s){
   int n = s.size();
   int lpsSize = lps(s, 0, n);
   return (n - lpsSize);
}
int main(){
   cout << "Minimum characters to be deleted = " <<
   minDeletion("abcda") << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Minimum characters to be deleted = 2