Print all palindromic partitions of a string

The problem, simply

A palindrome is a word that reads the same forwards and backwards, like level or noon. A single letter is always a palindrome.

You get a string. Cut it into pieces, keeping the letters in order, so that every piece is a palindrome. Give back every possible way to cut it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every first piece. If it is a palindrome, keep it and cut the rest the same way. Check each piece with two fingers, one at each end, walking inwards.

1. If the start is at the end of the word, the current list of pieces is an answer.
2. For every end from start to the last letter, check if s[start..end] is a palindrome.
3. If it is, add the piece, cut the rest from end + 1, then remove the piece again.

import java.util.*;

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

    private void cut(String s, int start, List<String> pieces, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(pieces));     // reached the end: one answer
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                pieces.add(s.substring(start, end + 1));
                cut(s, end + 1, pieces, result);
                pieces.remove(pieces.size() - 1);    // tape the piece back on
            }
        }
    }

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

How long it takes: there are up to 2^(n-1) ways to cut, and each answer costs up to n to check and copy, so O(n * 2^n). The same piece is checked again and again in different branches. Extra room: the list of pieces and the call stack, O(n).

Way 2: the clever way

The same pieces get checked over and over. So first fill a table that answers "is s[i..j] a palindrome?" for every i and j. Then the search reads the table instead of walking the piece.

A piece is a palindrome when its two end letters match and the part inside is a palindrome. A piece of one or two matching letters has nothing inside.

1. Fill pal[i][j] for i from the last letter down to the first, and j from i to the end: pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]).
2. Run the same cutting search, but use pal[start][end] as the check.

import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // ends match, and the inside is empty, one letter, or a palindrome
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            }
        }
        List<List<String>> result = new ArrayList<>();
        cut(s, 0, pal, new ArrayList<>(), result);
        return result;
    }

    private void cut(String s, int start, boolean[][] pal,
                     List<String> pieces, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(pieces));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!pal[start][end]) continue;          // one table look-up, no walking
            pieces.add(s.substring(start, end + 1));
            cut(s, end + 1, pal, pieces, result);
            pieces.remove(pieces.size() - 1);
        }
    }
}

How long it takes: the table costs O(n^2). The search is still O(n * 2^n) in the worst case, because the answer itself can be that big (think of aaaa...). But every check is now one look-up. Extra room: the table, O(n^2).

Watch out for

• Adding pieces itself to the answer. It keeps changing. Add a copy.
• Using substring(start, end) and forgetting it stops before end. The piece is substring(start, end + 1).
• The empty string. It has one way to cut: no pieces at all, so return [[]]. Say what you return.

What interviewers ask next

• Fewest cuts so every piece is a palindrome (Palindrome Partitioning II). Use the same table plus cuts[j] = min(cuts[i - 1] + 1) over every palindrome s[i..j]. That is O(n^2), no backtracking.
• Only count the ways. ways[j] adds up ways[i] for every palindrome s[i..j-1]. Also O(n^2).
• Can you build the table without extra rows? Yes, expand around each center, one letter or the gap between two letters, and mark every palindrome you grow. Same O(n^2).
• Longest palindrome inside the string. The table gives it in O(n^2). Manacher's algorithm does it in O(n).

Remember this

Grown-up words: the pieces form a partition, the mirror words are palindromes, cutting and taping back is backtracking, and the yes or no table is a 2D dynamic programming table.