mediumBacktracking

Palindrome Partitioning

Split a string into every possible sequence of palindromic substrings.

LeetCode ↗

Work through the cases

3 examples

Input notation

One nonempty lowercase string of at most 12 characters.

Expected result

Each partition on a line with | between pieces; sort the resulting lines alphabetically.

Case 1

Input

aab

Expected output

aa|b
a|a|b

Case 2

Input

ab

Expected output

a|b

Case 3

Input

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

List every way to cut s into palindromic pieces. n ≤ 16, so at most 2^{n-1} partitions; backtracking is fine. Checking palindromes at each cut rescans the same spans. Precompute f[i][j] whether s[i..j] is a palindrome, then try the next cut only when f[i][j] is true.

We can use dynamic programming to preprocess whether any substring in the string is a palindrome, i.e., f[i][j] indicates whether the substring s[i..j] is a palindrome.

Next, we design a function dfs(i), which represents starting from the i-th character of the string and partitioning it into several palindromic substrings, with the current partition scheme being t.

If i = |s|, it means the partitioning is complete, and we add t to the answer array and then return.

Otherwise, we can start from i and enumerate the end position j from small to large. If s[i..j] is a palindrome, we add s[i..j] to t, then continue to recursively call dfs(j+1). When backtracking, we need to pop s[i..j].

The time complexity is O(n × 2^n), and the space complexity is O(n^2). Here, n is the length of the string.

class Solution {
    private int n;
    private String s;
    private boolean[][] f;
    private List<String> t = new ArrayList<>();
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = s.charAt(i) == s.charAt(j) && f[i + 1][j - 1];
            }
        }
        this.s = s;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                t.add(s.substring(i, j + 1));
                dfs(j + 1);
                t.remove(t.size() - 1);
            }
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.