数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中查找通过移除或重排字符串字符形成的最长回文
概念
对于给定的字符串，确定可以通过移除或重排字符形成的最长回文。如果存在多个长度相同的最长回文字符串，则最终只返回一个回文。
输入
pqr
输出
p OR q OR r
输入
ppqqrr
输出
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
输入
pqp
输出
pqp
方法
在这里，我们可以将任何回文字符串分成三部分——开头、中间和结尾。对于长度为 2n + 1 的奇数回文字符串，'开头'包含字符串的前 n 个字符，'中间'只包含 1 个字符，即第 (n + 1) 个字符，'结尾'包含回文字符串的最后 n 个字符。对于长度为 2n 的偶数回文字符串，'中间'将始终为空。我们已经知道，为了使字符串成为回文，'结尾'将是'开头'的反向顺序。现在的概念是在我们的解决方案中实现上述观察结果。因为允许字符的重排，所以输入字符串中字符的顺序无关紧要。现在我们首先获取输入字符串中每个字符的频率。之后，输入字符串中所有出现次数为偶数 (例如 2n) 的字符都将成为输出字符串的一部分，因为我们可以很容易地将 n 个字符设置在'开头'字符串中，并将其他 n 个字符设置在'结尾'字符串中（通过保持回文的顺序）。对于出现次数为奇数 (例如 2n + 1) 的字符，我们将'中间'用所有这些字符中的一个填充，其余 2n 个字符分成两半，分别添加到开头和结尾。
示例
// C++ program to find the longest palindrome by removing
// or shuffling characters from the given string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find the longest palindrome by removing
// or shuffling characters from the given string
string findLongestPalindrome(string str1){
// Indicated to stores freq of characters in a string
int count1[256] = { 0 };
// Determine freq of characters in the input string
for (int i = 0; i < str1.size(); i++)
count1[str1[i]]++;
// Shows any palindromic string consisting of three parts
// beg1 + mid1 + end1
string beg1 = "", mid1 = "", end1 = "";
//Here solution assumes only lowercase characters are
// present in string. We can easily extend this
// to consider any set of characters
for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
// Now if the current character freq is odd
if (count1[ch1] & 1){
// Here mid1 will contain only 1 character. It
// will be overridden with next character
// with odd freq
mid1 = ch1;
// Here decrement the character freq to make
// it even and consider current character
// again
count1[ch1--]--;
}
// Here if the current character freq is even
else{
// Now if count is n(an even number), push
// n/2 characters to beg string and rest
// n/2 characters will form part of end
// string
for (int i = 0; i < count1[ch1]/2 ; i++)
beg1.push_back(ch1);
}
}
// Here end will be reverse of beg
end1 = beg1;
reverse(end1.begin(), end1.end());
// Now return palindrome string
return beg1 + mid1 + end1;
}
// Driver code
int main(){
string str1 = "pqqprrs";
cout << findLongestPalindrome(str1);
return 0;
}输出
pqrsrqp
更新于：2020年7月24日
136 次浏览
广告