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

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" ]

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 --------