# Palindromic Decomposition of a String Problem

Find all palindromic decompositions of a given string s.

A palindromic decomposition of string is a decomposition of the string into substrings, such that all those substrings are valid palindromes.

##### Example

Output: [ "a|b|r|a|c|a|d|a|b|r|a", "a|b|r|a|c|ada|b|r|a", "a|b|r|aca|d|a|b|r|a" ]

##### Notes

Input Parameters: There is only one argument: string s.

Output: Return array of string res, containing ALL possible palindromic decompositions of given string. To separate substrings in the decomposed string, use '|' as a separator between them.

• You need not to worry about the order of strings in your output array. Like for s = "aa", arrays ["a|a", "aa"] and ["aa", "a|a"] both will be accepted.

• In any string in your returned array res, order of characters should remain the same as in the given string. (i.e. for s = "ab" you should return ["a|b"] and not ["b|a"].)

• Any string in the returned array should not contain any spaces. e.g. s = "ab" then ["a|b"] is expected, ["a |b"] or ["a| b"] or ["a | b"] will give the wrong answer.

##### Constraints:

• 1

• s only contains lowercase letters ('a' - 'z').

Any string is its own substring.

#### Solution

We have provided two solutions:

1) Recursive solution: other_solution.cpp.

2) Dynamic programming solution: optimal_solution.cpp.

Try to solve the problem using both approaches.

In the dynamic programming solution we have pre-calculated is_palindrome array. In the recursive solution we have not done that only to make it easier to understand (you should do that there too).

Dynamic programming solution: optimal_solution.cpp

##### Time Complexity:

O((2^(n-1)) * n).

Worst case are strings like "aaaaaaaaaaaaaaaaaaaa", every substring there is a palindrome.

##### Auxiliary Space:

O((2^(n-1)) * n).

Answer array stores 2^(n-1) palindromic decompositions (in the worst case anyway) of length O(n).

Also is_palindrome array is O(n^2).

O((2^(n-1)) * n) + O(n^2) = O((2^(n-1)) * n).

##### Space Complexity Of The Optimal Solution:

O((2^(n-1)) * n).

Auxiliary space used is O((2^(n-1)) * n) and input size is O(n).

O((2^(n-1)) * n) + O(n) = O((2^(n-1)) * n).

``````
# -------- START --------

def generate_palindromic_decompositions(string):
if not string or len(string) == 1:
return [string]

output = []
n = len(string)

def _palindromic_decomposition(so_far, start):
# base case
if start == n:
output.append('|'.join(so_far))
return

# take every possible string from the current position and if it's palndromic go forward, and if it's not prune
for i in range(start+1, n+1):
curr = string[start:i]
if is_palindrome(curr):
so_far.append(curr)
_palindromic_decomposition(so_far, i)
# at the end of dfs remove what was appended to
so_far.pop()

_palindromic_decomposition([], 0)
return output

def is_palindrome(string):
if not string or len(string) == 1:
return True

low, high = 0, len(string) - 1
while low < high:
if string[low] != string[high]:
return False
low += 1
high -= 1

return True

def is_palindrome_rec(string):
if len(string) == 0:
return True
return _is_palindrome(string, 0, len(string)-1)

def _is_palindrome(string, start, end):
# empty string or string of 1 character
if start == end or start > end:
return True

return string[start] == string[end] and _is_palindrome(string, start+1, end-1)

# -------- END --------
``````

All Posts