数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用 C++ 打印字符串的所有回文排列
在这个问题中，我们得到一个字符串，我们必须打印该字符串字符的所有可能的回文排列。
让我们举个例子来理解这个问题：
输入：字符串 = ‘aabb’
输出：abba baab
为了解决这个问题，我们必须获取字符串的字符，并使用这些字符逐个生成所有回文字符串。
步骤 1：检查字符串是否为回文，如果不是，则打印“不可能”。
步骤 2：如果可以构成回文，则将其分成两半，并按字典序选择字符串的每个字母。
步骤 3：遍历创建的排列，对于偶数长度的字符串，反转一半；对于奇数频率，奇数字符应该位于中间以创建回文。
步骤 4：打印所有创建的回文。
实现算法的程序：
示例
#include <bits/stdc++.h>
using namespace std;
#define M 26
bool isPalindrome(string str, int* freq){
memset(freq, 0, M * sizeof(int));
int l = str.length();
for (int i = 0; i < l; i++)
freq[str[i] - 'a']++;
int odd = 0;
for (int i = 0; i < M; i++)
if (freq[i] % 2 == 1)
odd++;
if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
return true;
else
return false;
}
string reverse(string str){
string rev = str;
reverse(rev.begin(), rev.end());
return rev;
}
void generatePalindromePermutation(string str){
int freq[M];
if (!isPalindrome(str, freq))
return;
int l = str.length();
string half ="";
char oddC;
for (int i = 0; i < M; i++) {
if(freq[i] % 2 == 1)
oddC = i + 'a';
half += string(freq[i] / 2, i + 'a');
}
string palindrome;
do {
palindrome = half;
if (l % 2 == 1)
palindrome += oddC;
palindrome += reverse(half);
cout<<palindrome<<endl;
}
while (next_permutation(half.begin(), half.end()));
}
int main() {
string str="abab";
cout<<"All palindrome permutations of "<<str<<" are :\n";
generatePalindromePermutation(str);
return 0;
}输出
All palindrome permutations of abab are : abba baab
更新于：2020年7月14日
326 次浏览
广告