資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中查詢透過移除或重排字串字元形成的最長迴文
概念
對於給定的字串，確定可以透過移除或重排字元形成的最長迴文。如果存在多個長度相同的最長迴文字串，則最終只返回一個迴文。
輸入
pqr
輸出
p OR q OR r
輸入
ppqqrr
輸出
pqrrqp OR qprrpq OR rqppqr OR any other palindromic string of length 6.
輸入
pqp
輸出
pqp
方法
在這裡，我們可以將任何迴文字串分成三部分——開頭、中間和結尾。對於長度為 2n + 1 的奇數迴文字串，'開頭'包含字串的前 n 個字元，'中間'只包含 1 個字元，即第 (n + 1) 個字元，'結尾'包含迴文字串的最後 n 個字元。對於長度為 2n 的偶數迴文字串，'中間'將始終為空。我們已經知道，為了使字串成為迴文，'結尾'將是'開頭'的反向順序。現在的概念是在我們的解決方案中實現上述觀察結果。因為允許字元的重排，所以輸入字串中字元的順序無關緊要。現在我們首先獲取輸入字串中每個字元的頻率。之後，輸入字串中所有出現次數為偶數 (例如 2n) 的字元都將成為輸出字串的一部分，因為我們可以很容易地將 n 個字元設定在'開頭'字串中，並將其他 n 個字元設定在'結尾'字串中（透過保持迴文的順序）。對於出現次數為奇數 (例如 2n + 1) 的字元，我們將'中間'用所有這些字元中的一個填充，其餘 2n 個字元分成兩半，分別新增到開頭和結尾。
示例
// C++ program to find the longest palindrome by removing
// or shuffling characters from the given string
#include <bits/stdc++.h>
using namespace std;
// Shows function to find the longest palindrome by removing
// or shuffling characters from the given string
string findLongestPalindrome(string str1){
// Indicated to stores freq of characters in a string
int count1[256] = { 0 };
// Determine freq of characters in the input string
for (int i = 0; i < str1.size(); i++)
count1[str1[i]]++;
// Shows any palindromic string consisting of three parts
// beg1 + mid1 + end1
string beg1 = "", mid1 = "", end1 = "";
//Here solution assumes only lowercase characters are
// present in string. We can easily extend this
// to consider any set of characters
for (char ch1 = 'a'; ch1 <= 'z'; ch1++){
// Now if the current character freq is odd
if (count1[ch1] & 1){
// Here mid1 will contain only 1 character. It
// will be overridden with next character
// with odd freq
mid1 = ch1;
// Here decrement the character freq to make
// it even and consider current character
// again
count1[ch1--]--;
}
// Here if the current character freq is even
else{
// Now if count is n(an even number), push
// n/2 characters to beg string and rest
// n/2 characters will form part of end
// string
for (int i = 0; i < count1[ch1]/2 ; i++)
beg1.push_back(ch1);
}
}
// Here end will be reverse of beg
end1 = beg1;
reverse(end1.begin(), end1.end());
// Now return palindrome string
return beg1 + mid1 + end1;
}
// Driver code
int main(){
string str1 = "pqqprrs";
cout << findLongestPalindrome(str1);
return 0;
}輸出
pqrsrqp
更新於：2020年7月24日
136 次瀏覽
廣告