🌱 Keegan's Digital Garden

131. Palindrome Partitioning

2 min read

📝 Problem Details

NOTE: this problem can be improved with Dynamic Programming - but for the purpose of learning backtracking this solution opts for the less optimal approach

input string s partition s such that every substring of the partition is a palindrome return all possible palindrome partitioning of s

💭What Were My Initial Thoughts?

- buzzword "all possible" indicates an enumeration backtracking problem
- choice, include char c from s or exclude it from construction of palindrome
- constraint
	- early exit if the substr does not conform to a palindrome
		- what are the rules of being a palidrome?
			- must read the same forward as it does backward
			- frequency of chars is even, except for the middle which can be single
	- i dont think we can reorder the elements in s to create a palindrome?
	- partitioning means that each possibility must be a vector of strings where the sum of the strings equates to the same characters in the original string

💡 Explanation of Solution

1️⃣ Base Case (Termination Condition)
- If `start == s.size()`, we have partitioned the whole string into palindromes → **Add to result**.

2️⃣ Recursive Case
- Try partitioning at every `i` from `start → s.size()`.
- If `s[start:i+1]` is a palindrome:
    1. **Include it** in the current partition.
    2. **Recurse on the remaining string (`i+1` onward).**
    3. **Backtrack** (remove last choice and explore other options).

⌛ Complexity Analysis

Time Complexity: O(n * 2^n)
- each palindrome validation per dfs call takes O(n)
- dfs traversal O(2^n)

Space Complexity: O(2^n) due to returning the partitions

💻 Implementation of Solution

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        dfs(s, 0, path, result);
        return result;
    }
 
private:
    void dfs(string& s, int start, vector<string>& path, vector<vector<string>>& result) {
        // Base case: if we've partitioned the entire string
        if (start == s.size()) {
            result.push_back(path);
            return;
        }
 
        // Try all possible partitions
        for (int end = start; end < s.size(); end++) {
            if (isPalindrome(s, start, end)) {  // Check palindrome on-the-fly
                path.push_back(s.substr(start, end - start + 1));  // Choose substring
                dfs(s, end + 1, path, result);  // Explore further partitions
                path.pop_back();  // Backtrack
            }
        }
    }
 
    bool isPalindrome(string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
};

Graph View