Palindrome Partitioning - Java Solution

1. Introduction

This blog post addresses the "Palindrome Partitioning" problem, a fascinating challenge that involves dividing a string into substrings such that each substring is a palindrome. This problem exemplifies the use of backtracking in string manipulation and partitioning.

Problem

Given a string s, the objective is to partition s into as many substrings as possible where each substring is a palindrome. The goal is to return all such possible palindrome partitionings of s.

2. Solution Steps

1. Use a backtracking approach to explore all possible partitions.

2. At each step, check if the current substring is a palindrome.

3. If it is, recursively continue to find palindromes in the remaining string.

4. Once the end of the string is reached, add the current partition to the result.

5. Backtrack and try different partitions.

6. Return all the palindrome partitions found.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning {
    public static void main(String[] args) {
        System.out.println(partition("aab")); // Example 1
        System.out.println(partition("a"));   // Example 2
    }

    // Function to find all palindrome partitioning of a given string
    public static List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), s, 0);
        return result;
    }

    // Helper function for backtracking
    private static void backtrack(List<List<String>> result, List<String> tempList, String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < s.length(); i++) {
                if (isPalindrome(s, start, i)) {
                    tempList.add(s.substring(start, i + 1));
                    backtrack(result, tempList, s, i + 1); // Recurse
                    tempList.remove(tempList.size() - 1); // Backtrack
                }
            }
        }
    }

    // Utility function to check if a substring is a palindrome
    private static boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }
}

Output:

Example 1: [["a", "a", "b"], ["aa", "b"]]
Example 2: [["a"]]

Explanation:

1. partition: This function initializes the process of finding all palindrome partitions of the given string.

2. It calls the backtrack function with the initial parameters.

3. backtrack: A recursive helper function that explores each possible partition. It checks if the current substring is a palindrome.

4. If the substring is a palindrome, it is added to the current partition list (tempList) and the function recurses with the remainder of the string.

5. The function backtracks by removing the last added substring, trying different combinations.

6. isPalindrome: A utility function that checks if a given substring is a palindrome.

7. The result is a list of lists, where each list represents a different partition of the string into palindromes.