Palindrome Partitioning medium

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Example 1

Input: s = "aab" Output: [["a","a","b"],["aa","b"]]

Example 2

Input: s = "a" Output: [["a"]]

Steps

1. Base Case: If the input string s is empty, return a list containing an empty list [[]]. This represents the case where there are no partitions for an empty string.

2. Recursive Approach: We will use backtracking to explore all possible partitions. For each character in the string, we consider two possibilities:

   • Include the character as the start of a new partition: Check if the substring from the current index to the end is a palindrome. If it is, recursively call the function on the remaining substring (excluding the current palindrome).
   • Exclude the character from the current partition: Recursively call the function on the remaining substring, starting from the next character.

3. Palindrome Check: We need a helper function IsPalindrome to efficiently check if a given substring is a palindrome.

4. Storing Results: We'll use a list of lists of strings to store all the valid palindrome partitions.

Explanation

The backtracking approach systematically explores all possible ways to partition the string. The IsPalindrome function ensures that only valid palindrome partitions are considered. Each recursive call explores a different partition, and the results are accumulated in the result list.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<string>> Partition(string s) {
        IList<IList<string>> result = new List<IList<string>>();
        Backtrack(s, 0, new List<string>(), result);
        return result;
    }

    private void Backtrack(string s, int startIndex, List<string> currentPartition, IList<IList<string>> result) {
        if (startIndex == s.Length) {
            result.Add(new List<string>(currentPartition)); // Add a copy to avoid modification
            return;
        }

        for (int i = startIndex; i < s.Length; i++) {
            string substring = s.Substring(startIndex, i - startIndex + 1);
            if (IsPalindrome(substring)) {
                currentPartition.Add(substring);
                Backtrack(s, i + 1, currentPartition, result);
                currentPartition.RemoveAt(currentPartition.Count - 1); // Backtrack: remove the last added substring
            }
        }
    }

    private bool IsPalindrome(string s) {
        int left = 0;
        int right = s.Length - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the string. This is because there can be up to 2^N possible partitions, and checking each partition takes O(N) time in the worst case (for palindrome check).

• Space Complexity: O(N * 2^N) in the worst case to store all possible palindrome partitions. The recursive call stack also contributes to space complexity, but its depth is at most N.