Palindrome Partitioning

Problem

Partition the input string s such that every substring of the partition is a palindrome. Return every possible partitioning.

Constraints

• 1 ≤ s.length ≤ 16
• s contains lowercase English letters

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def partition(self, s):
        res = []
        def bt(start, cur):
            if start == len(s):
                res.append(cur[:]); return
            for end in range(start + 1, len(s) + 1):
                seg = s[start:end]
                if seg == seg[::-1]:
                    cur.append(seg)
                    bt(end, cur)
                    cur.pop()
        bt(0, [])
        return res

Java

import java.util.*;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> out = new ArrayList<>();
        bt(out, new ArrayList<>(), s, 0);
        return out;
    }
    private void bt(List<List<String>> out, List<String> cur, String s, int i) {
        if (i == s.length()) { out.add(new ArrayList<>(cur)); return; }
        for (int j = i; j < s.length(); j++) {
            if (isPalin(s, i, j)) {
                cur.add(s.substring(i, j + 1));
                bt(out, cur, s, j + 1);
                cur.remove(cur.size() - 1);
            }
        }
    }
    private boolean isPalin(String s, int l, int r) {
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.