LeetCode. 131. Palindrome Partitioning

Problem link

Precompute palindromic substrings, then backtrack

Let palindrome[left][right] indicate whether the inclusive substring s[left..right] is a palindrome. A substring is palindromic exactly when its endpoint characters match and either it has at most two characters or its inner substring is also palindromic:

palindrome[left][right] = (s.charAt(left) == s.charAt(right)) && (right - left < 2 || palindrome[left + 1][right - 1])

Fill the table with left moving from right to left. This ensures the shorter inner interval has already been computed. The table takes O(n^2) time and space.

Backtracking builds one partition from left to right. At each starting index, try every ending index whose substring is marked palindromic, append that substring, and recurse from the next index. When the start reaches n, copy the current path as one complete partition. The base case also handles an empty input: it adds the empty path, so partition("") returns one empty partition. The search has at most 2^(n-1) complete partitions for nonempty input; excluding the result strings and their construction, DFS uses O(n) path/stack space. Overall time is O(n^2 + n * 2^n) in the worst case including the output strings, and auxiliary space is O(n^2).

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

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] palindrome = new boolean[n][n];

        for (int left = n - 1; left >= 0; left--) {
            for (int right = left; right < n; right++) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right)
                        && (right - left < 2 || palindrome[left + 1][right - 1]);
            }
        }

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

    private void backtrack(
            String s,
            int start,
            boolean[][] palindrome,
            List<String> path,
            List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (!palindrome[start][end]) {
                continue;
            }
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, palindrome, path, result);
            path.remove(path.size() - 1);
        }
    }
}