C++에서 문자열 회문을 만드는 데 필요한 최소 추가 수

문제 설명

문자열이 주어지면 문자열 회문을 만들기 위해 추가할 최소 문자를 찾습니다.

예

string이 abcac이면 2개의 강조표시된 문자, 즉 abcacba

알고리즘

• 문자열이 이미 회문인지 확인하고, 그렇다면 문자를 추가할 필요가 없습니다.
• 문자열에서 문자를 하나씩 제거하고 나머지 문자열이 회문인지 확인
• 문자열이 회문석이 될 때까지 위의 과정을 반복합니다.
• 최종 답변으로 지금까지 제거된 문자 수를 반환합니다.

예

#include <iostream>
#include <cstring>
using namespace std;
bool isPalindrome(char *str) {
   int n = strlen(str);
   if (n == 1) {
      return true;
   }
   int start = 0, end = n - 1;
   while (start < end) {
      if (str[start] != str[end]) {
         return false;
      }
      ++start;
      --end;
   }
   return true;
}
int requiredAppends(char *str) {
   if (isPalindrome(str)) {
      return 0;
   }
   return 1 + requiredAppends(str + 1);
}
int main() {
   char *str = "abcac";
   cout << "Characters to be appended = " << requiredAppends(str) << endl;
   return 0;
}

출력

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

Characters to be appended = 2