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. Backtracking: We'll use a backtracking algorithm to explore all possible partitions.

  2. IsPalindrome Check: A helper function isPalindrome(s) will efficiently determine if a given substring is a palindrome.

  3. Recursive Exploration: The main function partition(s) will recursively explore all possible partitions:

    • For each index i from 0 to the length of the string:
      • Check if the substring from 0 to i is a palindrome.
      • If it is, add it to the current partition.
      • Recursively call partition on the remaining substring (from i+1 to the end).
      • Remove the last added palindrome from the current partition (backtracking step) to explore other possibilities.

  4. Result Storage: The results (lists of palindrome partitions) are stored in a list called result.

Explanation

The backtracking approach systematically explores all possible ways to divide the string into palindromes. It's crucial to understand the backtracking step: after exploring a partition with a particular palindrome, we remove that palindrome from the current partition to allow the exploration of other possible partitions. This ensures that all possibilities are covered without redundant computations. The isPalindrome check optimizes the process by preventing unnecessary recursive calls if a substring is not a palindrome.

Code

def isPalindrome(s):
    return s == s[::-1]

def partition(s):
    result = []
    currentPartition = []

    def backtrack(index):
        if index == len(s):
            result.append(currentPartition.copy())
            return

        for i in range(index, len(s)):
            substring = s[index:i+1]
            if isPalindrome(substring):
                currentPartition.append(substring)
                backtrack(i + 1)
                currentPartition.pop()

    backtrack(0)
    return result


#Example Usage
s = "aab"
print(partition(s))  # Output: [['a', 'a', 'b'], ['aa', 'b']]

s = "a"
print(partition(s))  # Output: [['a']]

s = "efe"
print(partition(s)) # Output: [['e', 'f', 'e'], ['efe']]

Complexity

  • Time Complexity: O(N * 2N), where N is the length of the string. This is because there can be up to 2N possible partitions, and checking if a substring is a palindrome takes O(N) in the worst case.
  • Space Complexity: O(N) due to the recursive call stack and the space needed to store the currentPartition and the result list. The space used by currentPartition is proportional to N in the worst case.