在C ++中打印字符串的所有回文排列

• Z时代
• 2024-01-10
• 分类：综合

在这个问题中，给了我们一个字符串，我们必须打印出该字符串中所有可能的回文排列。

让我们以一个例子来了解问题-

输入： string ='aabb'

输出： abba baab

为了解决这个问题，我们必须采用字符串的字符，并使用这些字符一一生成所有回文字符串。

步骤1-检查字符串是否是回文，如果不是，则打印“ Not不可能”。

步骤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

以上是 在C ++中打印字符串的所有回文排列 的全部内容， 来源链接： utcz.com/z/327320.html