Mündəricat
Bir sətir verilmiş, verilən bir sətrin bütün palindromik bölmələrini çap edəcək bir funksiya yazın
misal
INPUT
s = "bcdcb"
ÇIXDI
['b', 'c', 'd', 'c', 'b']
['b', "cdc", 'b']
[“Bcdcb”]
Bu metodda əsas fikir vektorlardan istifadə etmək, bütün bölmələri saxlamaq üçün 2 ölçülü bir vektor və cari bölməni saxlamaq üçün 1 ölçülü bir vektor yaratmaqdır.
Alqoritm
1. İlk şaratordan başlayaraq hər alt simdən keçin
2. Substring palindromdursa, onu həllinə əlavə edin
3. qalan hissə üçün təkrarlayın
C ++ Proqramı
#include<bits/stdc++.h>
using namespace std;
//function to check if s is palindroem
bool isPalindrome(string s, int start, int end)
{
while (start < end)
{
if (s[start++] != s[end--])
return false;
}
return true;
}
//Recursive function,
//sol is a vector of vectors, each vector store a partition
//cPartition is a vector of strings to store current partition
void recAllPPartitions(vector<vector<string> >&sol, vector<string> &cPartition,
int start, int n, string s)
{
// If 'start' has reached len
if (start >= n)
{
sol.push_back(cPartition);
return;
}
// Pick all possible ending points for substrings
for (int i=start; i<n; i++)
{
// If substring s[start..i] is palindrome
if (isPalindrome(s, start, i))
{
// Add the substring to result
cPartition.push_back(s.substr(start, i-start+1));
// Recur for remaining remaining substring
recAllPPartitions(sol, cPartition, i+1, n, s);
// Remove substring s[start..i] from current
// partition
cPartition.pop_back();
}
}
}
// Function to print all possible palindromic partitions of
// s. It mainly creates vectors and calls allPalPartUtil()
void printAllPPartitions(string s)
{
int n = s.length();
// To Store all palindromic partitions
vector<vector<string> > sol;
// To store current palindromic partition
vector<string> cPartition;
// to generate all partitions
recAllPPartitions(sol, cPartition, 0, n, s);
// Print all partitions
for (int i=0; i< sol.size(); i++ )
{
cout<<"[ ";
for (int j=0; j<sol[i].size(); j++)
cout << sol[i][j] << " ";
cout<<"]";
cout <<endl;
}
}
// Driver program
int main()
{
string s = "bcdcb";
printAllPPartitions(s);
return 0;
}Yoxla
