Leetcode 131. Palindrome Partitioning

Problem

Leetcode 131 - Palindrome Partitioning

Example:

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

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

Approach

We can solve this problem by using DFS and checking if the string is a palindrome with a helper function

Since we want separate array for different level (meaning how many characters) we can do this for each loop

Here is the Python code for the solution:

class Solution:
    def partition(self, s: str) -> List[List[str]]: 
        res = []
        part = []

        def dfs(i):
            if i >= len(s):
                res.append(part.copy())
                return
            
            for j in range(i, len(s)):
                if self.check(s, i, j):
                    part.append(s[i:j+1])
                    dfs(j+1)
                    part.pop()
        
        dfs(0)
        return res
    
    def check(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l, r = l+1, r-1
        return True

Time Complexity and Space Complexity

Time Complexity: $O(n*2^n)$

Space Complexity: $O(n*2^n)$