Finding palindromic decomposition of a String

Question

I am trying to solve palindromic decomposition of a string. I want to solve it using recursion. Here are some of the conditions.

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| <= 20 s only contains lowercase letters ('a' - 'z').

Any string is its own substring.

Here is the python code. Can you please provide a simpler strategy to solve this problem. I also require list of books, links to learn algorithm implementations using python for solving these kind of problems and also dynamic programming.

def isPalindrome(X, i, j):
 
    while i <= j:
        if X[i] != X[j]:
            return False
        i = i + 1
        j = j - 1
 
    return True
 
# Recursive function to find the minimum cuts needed in a String
# such that each partition is a palindrome
def minPalinPartition(X, i, j):
 
    # base case: if starting index i and ending index j are equal
    # or X[i..j] is already a palindrome.
    if i == j or isPalindrome(X, i, j):
        return 0
 
    # stores minimum number cuts needed to partition X[i..j]
    min = float('inf')
 
    # take the minimum over each possible position at which the
    # can be cut
 
    """
        (X[i]) | (X[i+1..j])
        (X[i..i+1]) | (X[i+2..j])
        (X[i..i+2]) | (X[i+3..j])
        ...
        ...
        (X[i..j-1]) | (X[j])
    """
 
    for k in range(i, j):
 
        # recur to get minimum cuts required in X[i..k] and X[k+1..j]
        count = 1 + minPalinPartition(X, i, k) + minPalinPartition(X, k + 1, j)
 
        if count < min:
            min = count
 
    # return the minimum cuts required
    return min
 

Answer 1

You could do it as a generator, like this:

def palinBreak(S):
    if len(S) == 1: yield S; return
    for n in range(1,len(S)+1):
        if S[:n] != S[:n][::-1]: continue
        yield from (S[:n]+"|"+pb for pb in palinBreak(S[n:]))


for pb in palinBreak("abracadabra"): print(pb)

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