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.This problem asks to find all possible ways to partition a given string s
such that each substring in the partition is a palindrome. The solutions presented use a backtracking approach, optimized with dynamic programming to efficiently check for palindromes.
Approach:
Palindrome Check (Dynamic Programming): The core idea is to precompute a boolean table f
where f[i][j]
is true
if the substring s[i:j+1]
is a palindrome, and false
otherwise. This is done efficiently using dynamic programming. The base cases are single characters (which are always palindromes), and the recursive relation is: f[i][j] = (s[i] == s[j]) and f[i+1][j-1]
. This means a substring is a palindrome if its first and last characters are the same, and the inner substring is also a palindrome.
Backtracking: After precomputing the f
table, a backtracking function dfs
explores all possible partitions. It starts at index 0 of the string. At each index i
, it iterates through all possible ending indices j
(such that j >= i
). If f[i][j]
is true (meaning s[i:j+1]
is a palindrome), it adds this substring to the current partition (t
), recursively calls dfs
to explore partitions starting from j+1
, and then backtracks by removing the substring from t
. This ensures that all possible combinations are explored.
Time and Space Complexity Analysis:
Time Complexity: The dynamic programming part takes O(n²) time to fill the f
table, where n is the length of the string. The backtracking part has a time complexity that's exponential in the worst case (e.g., string "aaaaaaaaa"), because it explores all possible partitions. However, it's bounded by the number of possible partitions, which is still exponential in the worst case. Overall, the dominant factor is the backtracking part, making the time complexity approximately O(2n) (exponential) in the worst case.
Space Complexity: The dynamic programming part requires O(n²) space for the f
table. The backtracking part uses the recursive call stack, whose depth is at most n. Additionally, the ans
list to store the results can also grow to a size determined by the number of possible partitions (also exponential in the worst case). Thus the space complexity is O(n² + 2n), dominated by the space for storing all the partition results in the worst case.
Code Explanation (Python as example, other languages are similar):
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
# DP table for palindrome checks
f = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
f[i][j] = s[i] == s[j] and f[i + 1][j - 1]
ans = [] # List to store all partitions
t = [] # Current partition
def dfs(i):
if i == n:
ans.append(t[:]) # Add a copy of the current partition
return
for j in range(i, n):
if f[i][j]: # If substring is a palindrome
t.append(s[i : j + 1]) # Add to current partition
dfs(j + 1) # Explore from next index
t.pop() # Backtrack: Remove the substring
dfs(0) # Start backtracking from index 0
return ans
The code first performs dynamic programming to efficiently check for palindromes. Then the backtracking function dfs
explores all combinations, adding palindromic substrings to the current partition and recursively calling itself until the end of the string is reached. Backtracking is used to explore other possibilities. The final list ans
contains all possible palindrome partitions.