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.
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
vector<vector<string>> res;
// Fill the DP table
for (int i = 0; i < n; ++i) dp[i][i] = true; // Single character palindrome
for (int length = 2; length <= n; ++length) {
for (int start = 0; start <= n - length; ++start) {
int end = start + length - 1;
if (length == 2)
dp[start][end] = (s[start] == s[end]);
else
dp[start][end] = (s[start] == s[end]) && dp[start + 1][end - 1];
}
}
vector<string> path;
backtrack(0, path, res, dp, s);
return res;
}
private:
void backtrack(int start, vector<string>& path, vector<vector<string>>& res, vector<vector<bool>>& dp, string& s) {
if (start == s.length()) {
res.push_back(path);
return;
}
for (int end = start; end < s.length(); ++end) {
if (dp[start][end]) {
path.push_back(s.substr(start, end - start + 1));
backtrack(end + 1, path, res, dp, s);
path.pop_back();
}
}
}
// Example Usage
// int main() {
// Solution sol;
// auto result = sol.partition("aab");
// for (const auto& partition : result) {
// for (const auto& part : partition) {
// cout << part << " ";
// }
// cout << endl;
// }
// }
};This C++ solution creates a dynamic programming table dp to determine if substrings are palindromes. It proceeds with a backtracking approach to explore all possible palindrome partitions. The precomputed dp table allows quick palindrome checks during partitioning, enhancing efficiency.