使用 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
廣告