C++에서 문자열 회문을 만들기 위한 최소 삽입 단계

문자열 s가 있다고 가정하고 이 문자열 회문을 만들어야 합니다. 각 단계에서 우리는 임의의 위치에 임의의 문자를 삽입할 수 있으며 이 회문을 만드는 데 필요한 최소 문자 수를 찾아야 합니다. 문자열이 "mad"와 같으면 "mad" 앞에 "da"를 추가하거나 "mad" 뒤에 "am"을 추가하여 이 회문을 만들 수 있으므로 답은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• lcs() 함수를 정의하면 s, x :=s가 필요합니다.
• n :=s의 크기
• 문자열 x 반전
• s :=s 앞에 공백 연결, x :=x 앞에 공백 연결
• (n + 1) x (n + 1) 크기의 2D 배열 dp 하나 정의
• 초기화 i:=1의 경우 i <=n일 때 업데이트(i를 1만큼 증가), 수행 -
  • j 초기화의 경우:=1, j <=n일 때 업데이트(j를 1만큼 증가), 수행 -
    • dp[i, j] :=dp[i – 1, j] 및 dp[i, j - 1]의 최대값
    • s[i]가 x[j]와 같으면 -
      • dp[i, j] :=dp[i, j] 및 dp[i – 1, j - 1] + 1의 최대값
• dp[n, n]을 반환
• 기본 메소드에서 s – lcs(s)의 크기를 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int lcs(string s){
      string x = s;
      int n = s.size();
      reverse(x.begin(), x.end());
      s = " " + s;
      x = " " + x;
      vector < vector <int> > dp(n + 1, vector <int>(n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n; j++){
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if(s[i] == x[j]){
               dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
         }
      }
      return dp[n][n];
   }
   int minInsertions(string s) {
      return s.size() - lcs(s);
   }
};
main(){
   Solution ob;
   cout << (ob.minInsertions("mad"));
}

입력

“mad”

출력

2