LC 131 - Palindrome Partitioning

Question

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"]]

Example 2:

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

Constraints:

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

Links

Question here and solution here

Solution

concept

We choose the partition as the first char as one partition and then recursively check the rest of the string. If the current string is a palindrome we will then proceed with DFS. Note the order of the algorithm here will do a,a,b in the first branch then backtrack to the top for loop and go down with aa, b.

code

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

        def dfs(i):
            if i >= len(s):
                ans.append(partition.copy())
                return

            for j in range(i, len(s)):
                if self.isPali(s, i, j):
                    partition.append(s[i:j+1])
                    dfs(j + 1)
                    partition.pop()
            
        dfs(0)
        return ans

    def isPali(self, s, l, r):
        while l < r:
            if s[l] != s[r]:
                return False
            l += 1
            r -= 1
        return True

Complexity

time: $O(n * 2^n)$
space: $O(2^n)$