CODEWITHSUNDEEP
pythonpython-3.xcombinations
Lupus
Lupus

Reputation: 33

Find all combinations of palindromic substrings

How to find all possible combinations of palindromic substrings for some randomly entered string in Python? For example, if entered xxyx what should be returned is : 

[['xx', 'y', 'x'], ['x', 'xyx'], ['x', 'x', 'y', 'x']] .

I know how to get all substrings and check if it is palindrome,but can`t find a way to combine into correct solution as shown. I am sorry if question isnt asked correctly, it's my first.

Here is the code: 

def find_all_subsets(seq, n):

    if n == 0:
        return [[]]

    else:
        result = []
        subsets = find_all_subsets(seq, n-1)

        for subset in subsets:
            result += [subset]

            result += [[seq[n-1]] + subset]

        return result


def check_palindrome(subsetsList):
    finalList = []
    for set in subsetsList:
        if set[::-1] == set:
            finalList.append(set)
        else:
           continue

    return finalList



if __name__ == "__main__":
    word = "xxyx"
    palindromicSubsets = check_palindrome(find_all_subsets(word, len(word)))
    print(palindromicSubsets)

Upvotes: 1

Views: 5425

Answers (1)

Blckknght
Blckknght

Reputation: 104712

It looks like you need to be looking not for all palindromic substrings, but rather for all the ways you can divide the input string up into palindromic substrings. (There's always at least one way, since one-character substrings are always palindromes.)

Here's the way I've done it:

def palindromic_substrings(s):
    if not s:
        return [[]]
    results = []
    for i in range(len(s), 0, -1):
        sub = s[:i]
        if sub == sub[::-1]:
            for rest in palindromic_substrings(s[i:]):
                results.append([sub] + rest)
    return results

There's two loops. The outer loop checks each length of initial substring (in descending length order) to see if it is a palindrome. If so, it recurses on the rest of the string and loops over the returned values, adding the initial substring to each item before adding it to the results.

A slightly more Pythonic approach would be to make a recursive generator:

def palindromic_substrings(s):
    if not s:
        yield []
        return
    for i in range(len(s), 0, -1):
        sub = s[:i]
        if sub == sub[::-1]:
            for rest in palindromic_substrings(s[i:]):
                yield [sub] + rest

Upvotes: 2

Related Questions