Sponsored
Sponsored
Recursive Backtracking: This approach involves using recursion to explore all possible ways to partition the string. At each position, we check all possible substrings starting from that position, and if a substring is palindrome, we recursively partition the remaining substring. This way, we build possible partitions incrementally.
Time Complexity: O(2n * n), since we can have 2^n possible partitions and checking each partition takes O(n).
Space Complexity: O(n), where n is the depth of the recursive call stack.
1def is_palindrome(s):
2 return s == s[::-1]
3
4def backtrack(start, path, res, s):
5 if start == len(s):
6 res.append(path[:])
7 return
8 for end in range(start + 1, len(s) + 1):
9 if is_palindrome(s[start:end]):
10 path.append(s[start:end])
11 backtrack(end, path, res, s)
12 path.pop()
13
14def partition(s):
15 res = []
16 backtrack(0, [], res, s)
17 return res
18
19# Example Usage
20# print(partition('aab'))This Python solution uses a helper function backtrack to perform recursive backtracking. We check each substring from the current position start. If it is a palindrome, we include it in our current path (path) and recursively continue partitioning the remainder of the string. If start reaches the end of the string, we add the current path to the results (res).
Dynamic Programming with Backtracking: This approach utilizes dynamic programming to precompute whether substrings are palindromes, reducing the on-the-fly palindrome check complexity in backtracking.
Time Complexity: O(n2 + 2n * n). Filling the dp table takes O(n2), and backtracking takes O(2n * n).
Space Complexity: O(n2), required for the dp table.
1def partition(s):
2 n =
This Python solution first uses dynamic programming to fill a table dp where dp[i][j] is True if the substring s[i:j+1] is a palindrome. Then, using backtracking, it generates partitions. If a substring s[start:end+1] is a palindrome (checked in O(1) time using dp), it adds it to the current path and continues recursively until the entire string is partitioned.