Palindrome Partitioning

medium string backtracking dp

Problem

Given a string s, partition it such that every substring is a palindrome. Return all possible partitions.

Inputs = "aab"

Output[["a","a","b"],["aa","b"]]

Two valid partitions, both made of palindromic pieces.

def partition(s):
    out, cur = [], []
    def is_pal(l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True
    def dfs(start):
        if start == len(s):
            out.append(cur[:]); return
        for end in range(start, len(s)):
            if is_pal(start, end):
                cur.append(s[start:end + 1])
                dfs(end + 1)
                cur.pop()
    dfs(0)
    return out

function partition(s) {
  const out = [], cur = [];
  const isPal = (l, r) => { while (l < r) { if (s[l] !== s[r]) return false; l++; r--; } return true; };
  function dfs(start) {
    if (start === s.length) { out.push(cur.slice()); return; }
    for (let end = start; end < s.length; end++) {
      if (isPal(start, end)) {
        cur.push(s.slice(start, end + 1));
        dfs(end + 1);
        cur.pop();
      }
    }
  }
  dfs(0);
  return out;
}

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

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> out;
        vector<string> cur;
        dfs(s, 0, cur, out);
        return out;
    }
    void dfs(const string& s, int start, vector<string>& cur, vector<vector<string>>& out) {
        if (start == (int)s.size()) { out.push_back(cur); return; }
        for (int end = start; end < (int)s.size(); end++) {
            if (isPal(s, start, end)) {
                cur.push_back(s.substr(start, end - start + 1));
                dfs(s, end + 1, cur, out);
                cur.pop_back();
            }
        }
    }
    bool isPal(const string& s, int l, int r) {
        while (l < r) { if (s[l] != s[r]) return false; l++; r--; }
        return true;
    }
};

Explanation

To split a string into palindromic pieces, we decide the first cut and then recursively split whatever remains. This explores every way to chop the string while making sure each piece is a palindrome.

The function dfs(start) means "split s from index start onward." It tries every possible end index, so the first piece is s[start..end]. If that piece is_pal (a palindrome), we add it to cur, recurse with dfs(end + 1) to split the rest, then pop it to backtrack and try a longer first piece.

When start reaches the end of the string, every piece we collected is a palindrome and together they cover the whole string, so we save a copy of cur as one valid partition.

Example: s = "aab". Cutting after the first a gives "a", then "a", then "b" → ["a","a","b"]. Cutting "aa" as one piece gives ["aa","b"]. Both are returned.

The palindrome check is_pal just compares characters from both ends moving inward, which is enough to validate each candidate piece.

Time: O(n · 2ⁿ) Space: O(n)