在C ++中构成字符串回文的最小删除数。
问题陈述
给定一个大小为'n'的字符串。任务是删除最少数量的字符以组成字符串回文。
如果给定的字符串是“abcda”，那么我们可以删除除第2个字符外的任何2个字符以使其成为回文。
如果我们删除字符“b”和“c”，则“ada”字符串是回文
如果我们删除字符“c”和“d”，则“aba”字符串是回文
如果我们删除字符“b”和“d”，则“aca”字符串是回文
算法
1. Find longest palindromic subsequence of given string. Let’s call it as “lpsSize”. 2. Minimum characters to be deleted = (length of string – lpsSize) Code.
示例
#include <iostream>
#include <algorithm>
using namespace std;
int lps(string s, int i, int j){
if (i == j) {
return 1;
}
if (s[i] == s[j] && i + 1 == j) {
return 2;
}
if (s[i] == s[j]) {
return lps(s, i + 1, j - 1) + 2;
}
return max(lps(s, i, j - 1), lps(s, i + 1, j));
}
int minDeletion(string s){
int n = s.size();
int lpsSize = lps(s, 0, n);
return (n - lpsSize);
}
int main(){
cout << "Minimum characters to be deleted = " <<
minDeletion("abcda") << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它生成以下输出-
Minimum characters to be deleted = 2
热门推荐
5 短祝福语简短暖心
10 结婚祝福语粤语大全简短
11 晚上祝福语女生文案简短
12 法语妈妈生日祝福语简短
13 药厂开工祝福语大全简短
14 蛋糕节日祝福语简短英文
15 跨年的生日祝福语简短
16 文案祝福语英文短句简短
17 在家聚餐婚礼祝福语简短
18 学生节祝福语大全简短