首页 > 代码库 > 构造回文 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。
构造回文 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子:
abcdagoogle
输出例子:
22
给出c++代码：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int LCS(const string &str1,const string &str2) {
if (str1 == "" || str2 == "")
return 0;
else
if (str1.back() == str2.back())
return LCS(str1.substr(0, str1.size() - 1), str2.substr(0, str2.size() - 1)) + 1;
else
return max(LCS(str1.substr(0, str1.size() - 1), str2.substr(0, str2.size())), LCS(str1.substr(0, str1.size()), str2.substr(0, str2.size() - 1)));
}
int main() {
string str1;
while (getline(cin,str1)) {
string str2(str1);
reverse(str1.begin(), str1.end());
cout<<str1.length()-LCS(str1, str2);
}
return 0;
}
构造回文 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。