131. Palindrome Partitioning

Medium LeetCode

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

Example 1

Input: s = "aab"

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

Explanation: The string "aab" can be partitioned as ["a","a","b"] where each substring is a palindrome, or as ["aa","b"] where "aa" is a palindrome and "b" is a palindrome.

Example 2

Input: s = "a"

Output: [["a"]]

Explanation: The single character "a" is already a palindrome, so the only partition is ["a"].

Constraints

• 1 <= s.length <= 16
• s contains only lowercase English letters

How to solve the problem

• Backtracking (DFS)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []  # To store all possible palindrome partitioning solutions
        path = []    # To store the current single partitioning solution
        n = len(s)

        # Helper function: checks if a string is a palindrome
        def is_palindrome(sub: str) -> bool:
            return sub == sub[::-1]

        # Depth-First Search (Backtracking) function
        def dfs(start_index: int):
            # Base case: if the start index reaches the end of the string,
            # it means we have found a valid complete palindrome partition.
            if start_index == n:
                # Add a copy of the current path to the result
                result.append(path.copy())
                return

            # From the start_index, try all possible partition points
            for i in range(start_index, n):
                # Get the substring
                substring = s[start_index : i + 1]
                
                # Check if the substring is a palindrome
                if is_palindrome(substring):
                    # If it's a palindrome, add it to the current path
                    path.append(substring)
                    
                    # Continue the DFS on the rest of the string
                    dfs(i + 1)
                    
                    # Backtrack: undo the choice to explore other possible partitions
                    path.pop()
        
        # Start the DFS from index 0
        dfs(0)
        return result

Complexity

• Time complexity: O(K*C(n, k))
• Space complexity: O(K*C(n, k))