Sweaty Imposter

Palindrome Partitioning

MediumBacktrackingNeetCode 150MidOpen on LeetCodeUpdated

You're given a string s. Split it into pieces so that every piece is a palindrome, and return every possible way to do so. Each answer is a list of substrings that, joined in order, spell s. The answers may be returned in any order.

Examples

s = "abb" returns [["a","b","b"],["a","bb"]]

"a" must stand alone, and the two bs can be split or kept together as "bb".

s = "abab" returns [["a","b","a","b"],["a","bab"],["aba","b"]]

Both "aba" and "bab" are palindromes, but they overlap, so no split uses both.

s = "x" returns [["x"]]

A single character is a palindrome.

Constraints

  • 1 <= s.length <= 16
  • s consists of lowercase English letters.

Hints

Hint 1

Every partition starts with some palindromic prefix of s. What is left to solve after you choose one?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Backtrack over cut positions. From index start, try every end index; if s[start..end] is a palindrome, add it to the path and recurse from end + 1. Reaching the end of the string means the path is a complete partition, so record a copy. Checking a palindrome with two pointers is O(n), and a string can have up to 2^(n - 1) partitions, so the total is O(n * 2^n) time with O(n) recursion depth. Precomputing a table of which substrings are palindromes makes each check O(1).

Time

O(n * 2^n)

Space

O(n)

Pitfall

Recording the path itself instead of a copy. Later pops and pushes change the same list, so every stored answer ends up empty or identical.

Solutions

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

    private void backtrack(String s, int start, List<String> path, List<List<String>> out) {
        if (start == s.length()) {
            out.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!isPalindrome(s, start, end)) continue;
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path, out);
            path.remove(path.size() - 1);
        }
    }

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