Find all possible Palindromic Partitions of the given String in Python

May 5, 2022

Palindromic Partitions of the given String in Python

Here on this page, We will learn How to Find All Possible Palindromic Partitions of the given String in Python Programming Language. We will discuss both approach and code on this page.

Algorithm

We go through every substring starting from the first character
Check if it is a palindrome
If yes, then add the substring to the solution
And recur for the remaining part

Python Code

Run

def isPalindrome(str, low, high):
    while low < high:
        if str[low] != str[high]:
            return False
        low += 1
        high -= 1
    return True


def allPalPartUtil(allPart, currPart, start, n, str):

    if start >= n:
        x = currPart.copy()
        allPart.append(x)
        return

    for i in range(start, n):
        if isPalindrome(str, start, i):
            currPart.append(str[start:i + 1])
            allPalPartUtil(allPart, currPart, i + 1, n, str)
            currPart.pop()


def allPalPartitions(str):

    n = len(str)
    allPart = []
    currPart = []
    allPalPartUtil(allPart, currPart, 0, n, str)

    for i in range(len(allPart)):
        for j in range(len(allPart[i])):
            print(allPart[i][j], end=" ")
        print()


string = "nitin"
allPalPartitions(string)

Output

n i t i n 
n iti n 
nitin

For similar Questions click on the given button