# Partition a String Into Palindromes - Backtracking / Pruning

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

I believe that time complexity is O(n*2^n) cause for every state we have to perform palindrome check which is o(n) doing loop for characters of substring.

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

1 Like

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
}
for(int i = 0; i < s.length(); i++){
if(isPalindrome(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!!!