C++ 中使字符串变为回文的最小追加次数

问题陈述

给定一个字符串，找出追加到它能使其变为回文的最小字符数。

示例

如果字符串为 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

更新日期： 2019 年 11 月 22 日

345 次浏览

开启您的 职业

完成课程获得认证

立即开始
广告