Cho chuỗi, in tất cả cách phân hoạch chuỗi thành các substring palindrome.
Input: "ababa" Output: ababa; a bab a; a b a b a ...
Giải pháp: Đệ quy backtracking. Tại mỗi vị trí, thử mọi substring bắt đầu từ đó, nếu là palindrome thì thêm vào phân hoạch hiện tại và đệ quy tiếp.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string str, int low, int high){
while (low < high) {
if (str[low] != str[high]) return false;
low++; high--;
}
return true;
}
void palindromePartition(vector<vector<string> >& allPart, vector<string>& currPart, int start, int n, string str){
if (start >= n) {
allPart.push_back(currPart);
return;
}
for (int i = start; i < n; i++){
if (isPalindrome(str, start, i)) {
currPart.push_back(str.substr(start, i - start + 1));
palindromePartition(allPart, currPart, i + 1, n, str);
currPart.pop_back();
}
}
}
void generatePalindromePartitions(string str){
int n = str.length();
vector<vector<string> > partitions;
vector<string> currPart;
palindromePartition(partitions, currPart, 0, n, str);
for (int i = 0; i < partitions.size(); i++) {
for (int j = 0; j < partitions[i].size(); j++)
cout << partitions[i][j] << " ";
cout << endl;
}
}
int main(){
string str = "abaaba";
cout << "Các phân hoạch palindrome:\n";
generatePalindromePartitions(str);
return 0;
}
Kết quả
a b a a b a a b a aba a b aa b a a baab a a b a aba aba aba abaaba