数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学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 次浏览
广告