C++で文字列回文を作成するために必要な追加の最小数

問題の説明

文字列を指定して、文字列回文を作成するために追加する最小文字を見つけます。

例

文字列がabcacの場合、2つのハイライト文字、つまりabcacbaを追加することで文字列回文を作成できます

アルゴリズム

• 文字列がすでに回文であるかどうかを確認します。ある場合は、文字を追加する必要はありません。
• 文字列から1文字ずつ削除し、残りの文字列が回文であるかどうかを確認します
• 弦がパリドロームになるまで上記のプロセスを繰り返します
• 最終回答までに削除された文字数を返します

例

#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