Find all possible palindromic partitions in a given string
💻 coding

Find all possible palindromic partitions in a given string

1 min read 189 words
1 min read
ShareWhatsAppPost on X
  • 1The article discusses using recursion to find all palindromic partitions of a given string.
  • 2A Java code example demonstrates how to implement the palindromic partitioning algorithm.
  • 3The output showcases various palindromic combinations from the input string 'askgifiga'.

AI-generated summary · May not capture all nuances

Key Insight
AskGif

"The article discusses using recursion to find all palindromic partitions of a given string."

Find all possible palindromic partitions in a given string

We will be using recursion for solving this problem. The idea is to navigate through each substring starting from first character and to check if it is a palindrome. If it is, then add the substring to solution list and do recur for remaining part. Below is code for solution in JAVA.

Example :

Input - "askgifiga"

Output - [[a, s, k, g, i, f, i, g, a], [a, s, k, g, ifi, g, a], [a, s, k, gifig, a]]
import java.util.Stack;

public class PallindromicPartition2 {

	static Stack<String> currList;
	static Stack<Stack> fullList;
	
	private static Boolean isPallindrom(String str,int start,int end) {
		while(start<=end) {
			if(str.charAt(start)!=str.charAt(end))
				return false;
			start++;
			end--;
		}
		return true;
	}
	private static void FindSubPalPartition(Stack<Stack> fullList, Stack<String> currList, int start, int end, String str) {
		if(start>=end) {
			Stack<String> currListClone = (Stack<String>) currList.clone();
			fullList.push(currListClone);
			return;
		}
		
		for(int i=start;i<end;i++) {
			if(isPallindrom(str,start,i)) {
				currList.push(str.substring(start, i+1));
				FindSubPalPartition(fullList, currList, i+1, end, str);
				currList.pop();
			}
		}
	}
	
	private static void FindAllPalPartition(String str) {
		int len = str.length();
		currList = new Stack<String>();
		fullList = new Stack<Stack>();
		
		FindSubPalPartition(fullList, currList, 0, len, str);
		System.out.println(fullList);
	}
	
	public static void main(String[] args) {
		String str = "askgifiga";
		FindAllPalPartition(str);
	}

}

Enjoyed this article?

Share it with someone who'd find it useful.

ShareWhatsAppPost on X

AskGif

Published on 13 July 2018 · 1 min read · 189 words

Part of AskGif Blog · coding

You might also like