Would you be able to explain in more detail how you got O(2^N)? Iâm not sure how to derive that from this question
The line where we call
dfs(i, path + [prefix])
Can someone explain why replacing the above line with the two below yields different results? The solution fails if you use the code below.
path.append(prefix)
dfs(i, path)
The total number of items would be 2^n with in all the varieties of partitions
a | a | c | d | c Do you see the potential partitions between characters? They can be either present (1) or not present (1). There are n-1 partitions, which means there are 2^(n-1) ways to partition the string. Im not so sure if its only O(2^n) as the palindrome check is already O(n).
When you do append, it makes the appended prefixes to the path permanent, compared to path + [prefix], which is temporarily adding it to the path list. Once the base case is reached, the prefixes are âpoppedâ from the path.
You can see the visualization here: https://tinyurl.com/2h4epa98
Hi, does anyone have a solution to do this with memoization?
Thereâs is never any backtracking here so memoization would not save any effort.
There are sub problems which can be memoized. Take case of a long string of aâs. <aaaaaaaaaaaaaaaaaaâŚ>
You can memoize all palindromes for a index. This will take more memory but would be faster.
You can memoize that for a index, there is only 1 palindrome chain i.e. each single character palindrome after that index. This will not take much memory but would stop wasted efforts for cases where there are no multi char palindromes after an index.
When I use custom input aabab
One of members of the ans is [âaâ,âaâ,âbabâ]
but a substring of âbabâ is âabâ which is not a palindrome, how does that work?
There is certainly backtracking here, indicated by the pushing and popping that is done in the loop. That represent âmaking a decisionâ and then âundoing the decisionâ. If you can backtrack, you can memoize. This section is called Backtracking as well so we better be backtracking! 
def partition(s: str) â List[List[str]]:
# WRITE YOUR BRILLIANT CODE HERE
start_idx = 0
path = []
ans = []
backtrack(start_idx, s, path, ans)
return ans
def is_palindrome(substring):
if substring == substring[::-1]:
return True
else:
return False
def backtrack(start_idx, s, path, ans):
if start_idx == len(s):
ans.append(path[:])
return
for end_idx in range(start_idx + 1, len(s)+1):
substring = s[start_idx: end_idx]
if substring and is_palindrome(substring):
path.append(substring)
backtrack(end_idx, s, path, ans)
path.pop()
I donât think the time complexity analysis is explained very well. A better way to think about it is to consider the worst case where we have a string that contains only one letter. Example: s = âaâŚaâ, and len(s) = n.
We can see that the number of ways to partition that string is 2^(n-1)
n=1: a => a
n=2: aa => aa or a|a
n=3: aaa => aaa or aa|a or a|aa or a|a|a
n=4: aaaa => aaaa or aaa|a or aa|aa or aa|a|a or a|aaa or a|aa|a or or a|a|aa or a|a|a|a
So O(2^n) is actually the SPACE COMPLEXITY of this problem.
If we want to determine the time complexity we cannot ignore the fact that it takes O(n) time to determine if a string is a palindrome. I wished there was a better explanation of why time complexity should be O(2^n). Specifically Iâd like to know what the template is to go from O(branching_factor ^ recursion depth) to O(2^n).
You are very welcome, this is a better understanding soloution
import java.util.List;
import java.util.Scanner;
import java.util.*;
class Solution {
public static List<List<String>> partition(String s) {
// WRITE YOUR BRILLIANT CODE HERE
List<List<String>> result = new ArrayList();
dfs(result, new ArrayList<String>(), s);
return result;
}
public static void dfs(List<List<String>> result, List<String> current, String s){
if(s.length() == 0)
{
//current is call by reference, so we need a copy before adding it to the result
result.add(new ArrayList(current));
}
for(int i = 0; i < s.length(); i++){
if(isPalindrome(s.substring(0 , i + 1))){
current.add(s.substring(0 , i + 1));
dfs(result,current,s.substring(i + 1));
current.remove(current.size() - 1);
}
}
}
public static boolean isPalindrome(String s) {
int low = 0 , high = s.length() - 1;
while (low < high) {
if (s.charAt(low++) != s.charAt(high--)) return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
scanner.close();
List<List<String>> res = partition(s);
for (List<String> row : res) {
System.out.println(String.join(" ", row));
}
}
}
Two Structured Programming JS Solutions Using Memo:
Solution 1:
function partition(str, memo = {}) {
const result = [];
if (str) {
if (memo[str]) {
result.push(...memo[str])
} else {
for (let i = 1; i <= str.length; i++) {
const prefix = str.slice(0, i);
if (isPalindrome(prefix)) {
for (const part of partition(str.slice(i), memo)) {
result.push([prefix, ...part]);
}
}
}
memo[str] = result;
}
}
return result.length
? result
: [[]];
}
Solution 2:
function partition(str, memo = {}) {
const result = [];
if (str) {
if (memo[str]) {
result.push(...memo[str]);
} else {
for (let i = 1; i <= str.length; i++) {
const prefix = str.slice(0, i);
if (isPalindrome(prefix)) {
const partitions = partition(str.slice(i), memo);
if (partitions.length == 0) {
result.push([prefix]);
} else {
for (const part of partitions) {
result.push([prefix, ...part]);
}
}
}
}
memo[str] = result;
}
} else {
result.push([]);
}
return result;
}
The explanation: get_edges: each letter is either 'a' or 'b'. should be something like get_edges: indexes for each new prefix from the remaining string'.
My solution mirroring the solution template:
def partition(s: str) â List[List[str]]:
output = []
n = len(s)
def get_edges(start_index):
return [s[start_index:i+1] for i in range(start_index, n)]
def is_valid(edge):
return edge == edge[::-1]
def is_leaf(idx):
return idx >= n
def dfs(idx, path):
if is_leaf(idx):
output.append(path[:])
return
for edge in get_edges(idx):
if not is_valid(edge):
continue
path.append(edge)
dfs(idx+len(edge), path)
path.pop()
dfs(0, [])
return output
yes itâs updated
Very well-explained code! Thanks a lot!!!
Hey byte, I just wanted to quickly thank you for the clear explanation. Your example of using a string with a single letter really helped me grasp the concept better, and your distinction between space and time complexity was particularly helpful.