Palindrome Partitioning - LeetCode Solution in Java

1. Introduction

"Palindrome Partitioning" is a problem that involves dividing a string into substrings, where each substring must be a palindrome. The challenge is to find all such possible partitionings.

2. Problem

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

3. Solution Steps

1. Use backtracking to explore all possible partitionings.

2. Start from the beginning of the string and explore each substring.

3. If a substring is a palindrome, add it to the current partition list and recurse for the remaining string.

4. Backtrack by removing the last partitioned palindrome after exploring.

5. Continue this process until the end of the string is reached.

4. Solution in Java

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), s, 0);
    return result;
}

private 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);
                tempList.remove(tempList.size() - 1); // Backtrack
            }
        }
    }
}

private boolean isPalindrome(String s, int low, int high) {
    while (low < high) {
        if (s.charAt(low++) != s.charAt(high--)) return false;
    }
    return true;
}

This solution uses backtracking to explore different ways of partitioning the string, ensuring that each substring in the partition is a palindrome. It incrementally builds partitions and backtracks to explore alternative possibilities.

Explanation:

1. The backtrack method is used to generate all possible partitionings.

2. It checks each substring of s, starting from start to i, for being a palindrome using isPalindrome.

3. If a substring is a palindrome, it is added to tempList, and backtrack is called recursively for the remaining string.

4. The process backtracks by removing the last added palindrome from tempList, allowing for the exploration of alternative partitionings.

5. Once the end of the string is reached (start == s.length()), the current partition list is added to the result.

6. isPalindrome checks if a substring is a palindrome by comparing characters from both ends towards the center.