Skip to content

131. Palindrome Partitioning

String Dynamic Programming Backtracking

Problem - Palindrome Partitioning

Medium

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.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[True] * n for _ in range(n)]
        result, temp = [], []
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]

        def dfs(i: int):
            if i == n:
                result.append(temp[:])
                return
            for j in range(i, n):
                if dp[i][j]:
                    temp.append(s[i : j + 1])
                    dfs(j + 1)
                    temp.pop()

        dfs(0)
        return result

Submission Stats:

  • Runtime: 36 ms (91.71%)
  • Memory: 34.6 MB (45.30%)