algoadvance

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:

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

Clarifying Questions

  1. Input constraints:
    • What is the length range of the input string s?
      • Typically, LeetCode constraints specify that 1 <= s.length <= 16.
    • Will the input string s contain only lowercase English letters?
      • Yes, usually.
  2. Output format:
    • Should the solution return lists of lists of strings?
      • Yes, it should return a list of lists where each list represents one possible palindrome partitioning.
  3. Edge cases:
    • How should the function handle an empty string?
      • If s is empty, the function should return a list containing an empty list, i.e., [[]].

Strategy

  1. Backtracking Approach:
    • Use a backtracking approach to explore all potential partitions of the string.
    • For each partition, check if the current substring is a palindrome.
    • If it is, recursively attempt to partition the remaining substring in the same way.
    • If the entire string is successfully partitioned into palindromes, add the current partition to the result.
  2. Palindrome Check Function:
    • Create a helper function to determine if a given substring is a palindrome.
  3. Base and Recursive Cases:
    • Base case: If we reach the end of the string, add the current path (partition) to the result list.
    • Recursive case: For each potential substring starting from the current position, if it forms a palindrome, recursively process the remaining substring.

Code

class Solution:
    def partition(self, s: str):
        res = []
        
        def is_palindrome(sub):
            return sub == sub[::-1]
        
        def backtrack(start, path):
            if start == len(s):
                res.append(path[:])
                return
            for end in range(start + 1, len(s) + 1):
                substring = s[start:end]
                if is_palindrome(substring):
                    path.append(substring)
                    backtrack(end, path)
                    path.pop()
        
        backtrack(0, [])
        return res

Explanation

  1. Palindrome Check: 
     def is_palindrome(sub):
     return sub == sub[::-1]
  2. Backtracking Function (backtrack):
    • start: index in the string s from where we start trying to partition.
    • path: stores the current list of palindromic substrings.
    • If start equals the length of s, it means we’ve partitioned the entire string, so we add the current path to res.
  3. We iterate over each possible ending position for a substring starting at the current start position.
    • If the substring from start to end is a palindrome, add it to the current path and recurse with the new start position (end).
    • After recursing, remove the last added substring to backtrack and explore other partitions.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com