数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 令字符串变为回文所需的最小删除次数。
问题陈述
给定一个大小为 ‘n’ 的字符串。目标是用最小字符删除使字符串变为回文。
如果给定字符串为 “abcda”，则我们可以删除除第一个和最后一个以外的任意 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
更新于： 31-Oct-2019
872 次浏览
广告