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.
Input: "abracadabra"
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" ]
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.
• 1
• s only contains lowercase letters ('a' - 'z').
Any string is its own substring.
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
O((2^(n-1)) * n).
Worst case are strings like "aaaaaaaaaaaaaaaaaaaa", every substring there is a palindrome.
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).
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).