資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 按字母順序列印給定字串的所有迴文排列
在這個問題中，我們得到一個大小為 n 的字串。我們必須按字母順序列印使用字串字元生成的所有可能的迴文排列。如果無法使用字串建立迴文，則列印“-1”。
讓我們舉個例子來更好地理解這個主題 -
Input: string = “abcba” Output : abcba bacba
現在，為了解決這個問題，我們需要找到所有可能的迴文，然後按字母順序（字典序）排列它們。或者另一種方法可能是找到由字串構成的字典序第一個迴文。然後找到序列中的下一個迴文。
為此，我們將執行以下步驟 -
步驟 1 - 儲存字串中所有字元出現的頻率。
步驟 2 - 現在檢查字串是否可以形成迴文。如果不是，列印“無法形成迴文”並退出。否則執行 -
步驟 3 - 基於以下邏輯建立一個字串：所有出現次數為偶數的字元形成一個字串，出現次數為奇數的字元形成另一個字串。我們將奇數字符串夾在偶數字符串之間（即以偶數字符串 + 奇數字符串 + 偶數字符串的形式）。
使用此方法，我們可以找到字典序第一個迴文。然後透過檢查併發字典序組合來找到下一個迴文。
示例
說明概念的程式 -
#include <iostream>
#include <string.h>
using namespace std;
const char MAX_CHAR = 26;
void countFreq(char str[], int freq[], int n){
for (int i = 0; i < n; i++)
freq[str[i] - 'a']++;
}
bool canMakePalindrome(int freq[], int n){
int count_odd = 0;
for (int i = 0; i < 26; i++)
if (freq[i] % 2 != 0)
count_odd++;
if (n % 2 == 0) {
if (count_odd > 0)
return false;
else
return true;
}
if (count_odd != 1)
return false;
return true;
}
bool isPalimdrome(char str[], int n){
int freq[26] = { 0 };
countFreq(str, freq, n);
if (!canMakePalindrome(freq, n))
return false;
char odd_char;
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 != 0) {
freq[i]--;
odd_char = (char)(i + 'a');
break;
}
}
int front_index = 0, rear_index = n - 1;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
char ch = (char)(i + 'a');
for (int j = 1; j <= freq[i] / 2; j++) {
str[front_index++] = ch;
str[rear_index--] = ch;
}
}
}
if (front_index == rear_index)
str[front_index] = odd_char;
return true;
}
void reverse(char str[], int i, int j){
while (i < j) {
swap(str[i], str[j]);
i++;
j--;
}
}
bool nextPalindrome(char str[], int n){
if (n <= 3)
return false;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (str[i] < str[i + 1])
break;
if (i < 0)
return false;
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (str[j] > str[i] && str[j] < str[smallest])
smallest = j;
swap(str[i], str[smallest]);
swap(str[n - i - 1], str[n - smallest - 1]);
reverse(str, i + 1, mid);
if (n % 2 == 0)
reverse(str, mid + 1, n - i - 2);
else
reverse(str, mid + 2, n - i - 2);
return true;
}
void printAllPalindromes(char str[], int n){
if (!(isPalimdrome(str, n))) {
cout<<"-1";
return;
}
do {
cout<<str<<endl;
} while (nextPalindrome(str, n));
}
int main(){
char str[] = "abccba";
int n = strlen(str);
cout<<”The list of palindromes possible is :\n”;
printAllPalindromes(str, n);
return 0;
}輸出
可能的迴文列表為 -
abccba acbbca baccab bcaacb cabbac cbaabc
更新於: 2020-01-17
225 次檢視
廣告