資料結構
網路
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 次瀏覽
廣告