Palindrome Partitioning

XXX.Palindrome Partitioning

Backtracking

Dynamic Programming

Problem Statement:

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

Algorithm:

1. Preprocess the input string using a dynamic programming matrix to determine if substrings are palindromes.
2. Use backtracking to explore all possible partitions:
   • At each step, if the substring is a palindrome, add it to the temporary list.
   • Recurse for the remaining substring.
   • Backtrack by removing the last added substring and explore other possibilities.
3. Add the valid partitions to the result list when the end of the string is reached.

Complexity:

Time: O(n × 2ⁿ), where n is the length of the string. The DP preprocessing runs in O(n²). | Space: O(n²) for the DP table and recursion stack.

Java Implementation:

class Solution {
    boolean[][] isPalindrome;

    public List> partition(String s) {
        // Precompute palindromes using a DP matrix
        isPalindrome = createPalindromeDPMatrix(s);

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

    // Backtracking function to generate all partitions
    public void backtrack(String s, List> result, List tempList, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(tempList)); // Add partition to result
            return;
        }

        for (int i = start; i < s.length(); i++) {
            // If substring is a palindrome, continue the partition
            if (isPalindrome[start][i]) {
                tempList.add(s.substring(start, i + 1)); // Add palindrome
                backtrack(s, result, tempList, i + 1);   // Recurse
                tempList.remove(tempList.size() - 1);    // Backtrack
            }
        }
    }

    // Helper function to preprocess palindromes using DP
    public boolean[][] createPalindromeDPMatrix(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true; // Mark substring as palindrome
                }
            }
        }
        return dp;
    }
}
                

Python Implementation:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def is_palindrome(s, left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left, right = left + 1, right - 1
            return True

        def backtrack(start, temp):
            if start == len(s):
                result.append(temp[:])
                return
            for end in range(start, len(s)):
                if is_palindrome(s, start, end):
                    temp.append(s[start:end + 1])
                    backtrack(end + 1, temp)
                    temp.pop()

        result = []
        backtrack(0, [])
        return result
                

C++ Implementation:

class Solution {
public:
    vector> partition(string s) {
        vector> result;
        vector temp;
        backtrack(s, 0, temp, result);
        return result;
    }

    void backtrack(string& s, int start, vector& temp, vector>& result) {
        if (start == s.size()) {
            result.push_back(temp);
            return;
        }
        for (int end = start; end < s.size(); ++end) {
            if (isPalindrome(s, start, end)) {
                temp.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1, temp, result);
                temp.pop_back();
            }
        }
    }

    bool isPalindrome(string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
};