We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindrome Partitioning

Difficulty: Medium

Problem Description

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

Key Insights

  • A palindrome reads the same forward and backward.
  • We can use a backtracking approach to explore all possible partitions of the string.
  • A helper function can check if a substring is a palindrome.
  • The constraints allow for a maximum string length of 16, making backtracking feasible.

Space and Time Complexity

Time Complexity: O(2^n) where n is the length of the string, since we potentially explore all partitions. Space Complexity: O(n) for the recursive call stack and O(k) for storing the current partition (where k is the number of partitions).

Solution

We will use a backtracking algorithm to explore all possible ways to partition the string into substrings that are palindromes. The algorithm involves:

  1. Iterating through the string to find possible palindrome substrings.
  2. Using a helper function to check if a substring is a palindrome.
  3. Recursively building partitions, and when a valid partition is found, adding it to the results.

The primary data structure used is a list to store the current partition of palindromes as we explore different partitions.

Code Solutions

def is_palindrome(s, start, end):
    while start < end:
        if s[start] != s[end]:
            return False
        start += 1
        end -= 1
    return True

def backtrack(start, path, result, s):
    if start == len(s):
        result.append(path[:])
        return
    for end in range(start, len(s)):
        if is_palindrome(s, start, end):
            path.append(s[start:end + 1])
            backtrack(end + 1, path, result, s)
            path.pop()

def partition(s):
    result = []
    backtrack(0, [], result, s)
    return result
← Back to All Questions