Palindrome Partitioning

Cut a string into pieces so that every piece reads the same forwards and backwards.

The idea

Try every prefix of what is left, starting from the shortest. If that prefix is a palindrome, cut it off, add it to the path, and solve the remaining suffix the same way. When nothing is left, the path is a complete partition.

Code

public static void Partition(string s, int start, List<string> path, List<List<string>> result) {
    if (start == s.Length) { result.Add(new List<string>(path)); return; }
    for (int end = start; end < s.Length; end++) {
        string piece = s.Substring(start, end - start + 1);
        if (!IsPalindrome(piece)) continue;
        path.Add(piece);
        Partition(s, end + 1, path, result);
        path.RemoveAt(path.Count - 1);
    }
}

static bool IsPalindrome(string s) {
    int i = 0, j = s.Length - 1;
    while (i < j) if (s[i++] != s[j--]) return false;
    return true;
}

Tips

• The loop tries every cut length, not just the first palindrome found, because a short match can block a better partition later on.
• Checking IsPalindrome before recursing, instead of inside the base case, avoids building paths that could never work.

In the .NET library

Testing a substring for being a palindrome is O(n) by itself, so a naive version re-checks the same substrings many times. A real solution precomputes a table of which (start, end) ranges are palindromes.