Partitioning Problems: Palidrome Partitioning and IP Restoration

Palindrome Partitioning (LeetCode 131)

Partition a string into substrings such that every substring is a palindrome. Return all possible solutions.

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    // Optimization: Pre-calculate palindrome statuses for all substrings
    boolean[][] isPalindrome = precompute(s);
    backtrack(s, 0, new ArrayList<>(), res, isPalindrome);
    return res;
}

private void backtrack(String s, int start, List<String> path, List<List<String>> res, boolean[][] dp) {
    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (dp[start][end]) {
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path, res, dp);
            path.removeLast();
        }
    }
}

private boolean[][] precompute(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1]);
        }
    }
    return dp;
}

Optimization Insight: Precomputing the palindrome grid using Dynamic Programming reduces the per-step check time from $O(N)$ to $O(1)$, resulting in an overall time complexity of $O(N \cdot 2^N)$.

Palindrome Partitioning II (LeetCode 132)

Find the minimum number of cuts needed.

Note: For "minimum" or "maximal" counts rather than full enumeration, use Dynamic Programming directly instead of backtracking to avoid exponential overhead.

public int minCut(String s) {
    int n = s.length();
    boolean[][] dp = precompute(s);
    int[] minCuts = new int[n];
    for (int i = 0; i < n; i++) {
        if (dp[0][i]) { minCuts[i] = 0; continue; }
        minCuts[i] = i; // Initial max cuts
        for (int j = 1; j <= i; j++) {
            if (dp[j][i]) minCuts[i] = Math.min(minCuts[i], minCuts[j - 1] + 1);
        }
    }
    return minCuts[n - 1];
}

Restore IP Addresses (LeetCode 93)

Partition a numeric string into 4 segments to form valid IP addresses.

public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<>();
    backtrack(s, 0, 0, new StringBuilder(), res);
    return res;
}

private void backtrack(String s, int start, int parts, StringBuilder current, List<String> res) {
    if (parts == 4 && start == s.length()) {
        res.add(current.substring(0, current.length() - 1)); // Remove trailing '.'
        return;
    }
    if (parts == 4 || start == s.length()) return;

    for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
        String segment = s.substring(start, start + len);
        // Pruning: Check for leading zeros and range 0-255
        if (segment.length() > 1 && segment.startsWith("0")) break;
        if (Integer.parseInt(segment) > 255) break;
        
        int lenDot = segment.length() + 1;
        current.append(segment).append('.');
        backtrack(s, start + len, parts + 1, current, res);
        current.delete(current.length() - lenDot, current.length()); // Backtrack
    }
}

Summary Selection Table