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.
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.