Palindrome Partitioning Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/palindromic-partitioning

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Find all possible ways of palindromic partitioning.

Approach

The approach to this problem is to use recursive backtrack to find every possible partition of the string and check which of the partitions have palindrome substrings only. We traverse the string from the start considering all the substrings and after finding a palindrome substring we search for the palindromes in the remaining string recursively.

Analysis 

• Time Complexity: Exponential
• Auxiliary Space Complexity: O(1)

Implementation

C++

bool isPalindrome(string &s, int start, int end)
{
    while (start < end)
    {
        if (s[start] != s[end]) {
            return false;
		}
        start++;
        end--;
    }
    return true;
}
void findAllPalindromes (string &s, int start, vector<string> &currentPalindrome, vector<vector<string>> &allPalindromes) {
	if(start >= s.size()) {
		allPalindromes.push_back(currentPalindrome);
		return;
	}
	for (int i = start; i < s.size(); i++) {
		if (isPalindrome(s, start, i)) {
			currentPalindrome.push_back(s.substr(start, i - start + 1));
			findAllPalindromes (s, i + 1, currentPalindrome, allPalindromes);
			currentPalindrome.pop_back();
		}
	}
}
vector<vector<string> > getPartitions(string s) {
    vector<vector<string>> allPalindromes;
	vector<string> currentPalindrome;
	findAllPalindromes (s, 0, currentPalindrome, allPalindromes);
	return allPalindromes;
}

Java

class Solution {
	boolean isPalindrome(String s, int start, int end)
	{
		while (start < end)
		{
			if (s.charAt(start) != s.charAt(end)) {
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
	void findAllPalindromes (String s, int start, List<String> currentPalindrome, List<List<String>> allPalindromes) {
		if(start >= s.length()) {
			allPalindromes.add(new ArrayList<> (currentPalindrome));
			return;
		}
		for (int i = start; i < s.length(); i++) {
			if (isPalindrome(s, start, i)) {
				currentPalindrome.add(s.substring(start, i + 1));
				findAllPalindromes (s, i + 1, currentPalindrome, allPalindromes);
				currentPalindrome.remove(currentPalindrome.size() - 1);
			}
		}
	}
	List<List<String>> getPartitions(String s) {
	    List<List<String>> allCombinations = new ArrayList<List<String>> ();
		List<String> currentCombination = new ArrayList<String> ();
		findAllPalindromes (s, 0, currentCombination, allCombinations);
		return allCombinations;
	}
}