使用 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 次檢視

啟動您的 職業生涯

完成課程獲得認證

開始學習
廣告