資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告