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.
1import java.util.*;
2
3public class Solution {
4 private boolean isPalindrome(String s, int low, int high) {
5 while (low < high) {
6 if (s.charAt(low++) != s.charAt(high--)) {
7 return false;
8 }
9 }
10 return true;
11 }
12
13 private void backtrack(int start, List<String> path, List<List<String>> res, String s) {
14 if (start == s.length()) {
15 res.add(new ArrayList<>(path));
16 return;
17 }
18 for (int end = start + 1; end <= s.length(); end++) {
19 if (isPalindrome(s, start, end - 1)) {
20 path.add(s.substring(start, end));
21 backtrack(end, path, res, s);
22 path.remove(path.size() - 1);
23 }
24 }
25 }
26
27 public List<List<String>> partition(String s) {
28 List<List<String>> res = new ArrayList<>();
29 backtrack(0, new ArrayList<>(), res, s);
30 return res;
31 }
32
33 // Example Usage
34 // public static void main(String[] args) {
35 // Solution sol = new Solution();
36 // System.out.println(sol.partition("aab"));
37 // }
38}This Java code uses a backtracking approach similar to the Python solution. The backtrack method partitions the string from a start index by checking each possible substring for palindromicity using the isPalindrome method. If a palindrome is found, it is added to the path, and the method is called recursively. Eventually, when the end of the string is reached, the current path is added to 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.