-
Notifications
You must be signed in to change notification settings - Fork 1k
/
Print_Palindrome_Partitions.cpp
79 lines (71 loc) · 1.75 KB
/
Print_Palindrome_Partitions.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
This problem is solved using backtracking.
It will print all possible Palindromes in the string
*/
#include <bits/stdc++.h>
using namespace std;
/*To check whether a given string is Palindrome or not*/
int isPalindrome(string& word)
{
int n = word.length() - 1;
for (int i = 0; i < n; i++) {
if (word[i] != word[n]) {
return false;
}
n--;
}
return true;
}
// Prototype of PalindromeUtil
void printPalindrome(string str, int n, string result);
// Prints all possible Palindromes of given string
void Palindrome(string str)
{
// Last argument is word
printPalindrome(str, str.size(), "");
}
/* Result store the current word with spaces
between words */
void printPalindrome(string str, int n, string result)
{
//Process all words one by one
for (int i = 1; i <= n; i++) {
// Extract substring from 0 to i in word
string word = str.substr(0, i);
/* If dictionary conatins this word, then
we check for remaining string. Otherwise
we ignore this word (there is no else for
this if) and try next */
if (isPalindrome(word)) {
// If no more elements are there, print it
if (i == n) {
// Add this element to previous word
result += word;
cout << result << endl;
return;
}
printPalindrome(str.substr(i, n - i), n - i, result + word + " , ");
}
}
}
int main()
{
// Function call
string str;
cin >> str;
Palindrome(str);
return 0;
}
/*
Input - abaaba
Output -
a , b , a , a , b , a
a , b , a , aba
a , b , aa , b , a
a , baab , a
aba , a , b , a
aba , aba
abaaba
Time Complexity - O(n^n)
Space Complexity - O(n*n)
*/