Palindrome Partitioning

Dec 18, 2024 • 4 mins read
Hero Image

Problem Overview

The problem "Palindrome Partitioning," hosted on LeetCode, revolves around finding all possible palindrome partitions of a given string. The task is to partition a string such that every substring of the partition is a palindrome. This problem showcases the utilization of recursive backtracking to explore every possible partition efficiently.

Understanding the Problem

A palindrome is a string that reads the same backward as forward, for instance, "radar" or "level". The aim is to split the input string into sections where each section is a palindrome. The output should be a list of lists, whereby each list represents a valid partitioning of the input string.

Example:

Input: "aab"

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

  • The input string "aab" can be partitioned into two possible ways such that each partition is a palindrome.

Key DSA Concepts and Theory

Recursion

Recursion is a fundamental concept in computer science where a function calls itself directly or indirectly. Recursive strategies are quite powerful for parsing complex problems into manageable parts, especially when dealing with permutations or combinations, as seen in this problem.

Backtracking

Backtracking is an algorithmic paradigm used to solve problems incrementally, trying partial solutions and then abandoning them if they are not feasible. This technique is well-suited for generating all possible candidates for solutions and then filtering out invalid ones.

Palindrome Check

A palindrome check is crucial for the problem. This involves a straightforward comparison of characters from both ends of the string moving towards the center.

Solution Approach

The essence of solving this problem is through recursive backtracking. The steps are as follows:

  1. Initialize a Recursive Function: This function will explore all possible ways to partition the string from a starting index.
  2. Base Case: If the starting index reaches the length of the string, add the current partition to the result.
  3. Recursive Exploration: Iterate over the string and partition it based on palindromic substrings.
  4. Check for Palindrome: Before recursing further on a substring, check if it is a palindrome.
  5. Recursion with Backtracking: Include the current palindrome in the path, recursively attempt to partition the remainder of the string, and backtrack by removing the last added palindrome to explore other options.

C++ Implementation

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        dfs(s, 0, path, result);
        return result;
    }

    void dfs(string &s, int index, vector<string> &path, vector<vector<string>> &result) {
        if (index == s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = index; i < s.size(); ++i) {
            if (isPalindrome(s, index, i)) {
                path.push_back(s.substr(index, i - index + 1));
                dfs(s, i + 1, path, result);
                path.pop_back();
            }
        }
    }

    bool isPalindrome(string &s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

Java Implementation

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

    private void dfs(String s, int index, List<String> path, List<List<String>> result) {
        if (index == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                path.add(s.substring(index, i + 1));
                dfs(s, i + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }

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

Time and Space Complexity Analysis

  • Time Complexity: The time complexity is O(N * 2^N), where N is the length of the string. The factor 2^N arises from generating all possible partitions, and multiplying by N is due to the palindrome checks.

  • Space Complexity: The space complexity is O(N), which arises from the space used by the recursive stack.

Common Mistakes to Avoid

  • Not correctly checking if the substring is a palindrome before recursing.
  • Forgetting to backtrack by removing the last palindrome substring from the current path.

Similar Problems on LeetCode

  • Restore IP Addresses (LeetCode 93)
  • Subsets (LeetCode 78)
  • Combination Sum (LeetCode 39)

Additional Resources and References