^ To explain a little more thoroughly, since we don’t know whether each branch will be pruned or not, we assume the worst case - that no branches will be pruned. This happens when our string is all the same character (i.e. “aaaaaaa”) and so every possible substring is a palindrome. In this case, our algorithm will have to explore every possible partition of the input string, so determining the runtime becomes a question of calculating how many possible partitions exist for a string of length n.
As Truong explains, you can either include a partition after the first character or not include one. For each of these possibilities, you can either include a partition after the second character or not include one. For each of these possibilities, you can either include a partition after the third character or not include one, and so on. So, the total number of possible partitions is 2 * 2 * 2 * 2… n-1 times, since there are n-1 spots where a partition could be inserted. So, the algorithm recurses through 2^(n-1) = O(2^n) possible partitions. For each one, it takes O(n) time to check if the string is a palindrome and generate the substring for the recursive call, depending on how you wrote your solution. So the overall time complexity is O(n*2^n).
Another way of doing this
def partition(s: str) -> List[List[str]]:
result = []
def is_palindrome(st):
return st == st[::-1]
def dfs(take, remain, path):
if len(remain) == 0:
if len(path) > 0:
result.append(path[:])
return
for index, value in enumerate(remain):
take = remain[0:index+1]
new_remain = remain[index+1:]
if is_palindrome(take):
path.append(take)
dfs(take, new_remain, path)
path.pop()
dfs("", s, [])
return result
Why doesn’t the creation of a new string in each recursive call influence the space complexity?
def partition(s: str) -> List[List[str]]:
def is_palindrome(s):
if not s:
return True
left, right = 0, len(s) - 1
while left <= right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def dfs(rst, cur_path, idx):
if idx == len(s):
rst.append(cur_path[:])
return
for i in range(idx+1, len(s)+1):
if not is_palindrome(s[idx: i]):
continue
cur_path.append(s[idx: i])
dfs(rst, cur_path, i)
cur_path.pop()
rst = []
dfs(rst, [], 0)
return rst
The part where I added the path values to the final result took me more than an hour to figure out why my solution wasn’t working. I was just adding the reference of the path to the final result.
result.add(path);
Here is my solution using Java
static List<List<String>> result = new ArrayList<List<String>>();
public static List<List<String>> partition(String s) {
dfs(s, 0, new ArrayList<>(), res);
return res;
}
public static void dfs(String s, int startIndex, List<String> path) {
if (startIndex == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (String edge : get_edges(startIndex, s)) {
if (!isValidPalindrom(edge)) {
continue;
}
path.add(edge);
dfs(s, startIndex + edge.length(), path);
path.remove(path.size()-1);
}
}
public static List<String> get_edges(int i , String val) {
List<String> edges = new ArrayList<>();
for (int j = i+1; j <= val.length(); j++) {
edges.add(val.substring(i, j));
}
return edges;
}
public static boolean isValidPalindrom (String val) {
String pal="";
for (int j = val.length()-1; j >=0; j--) {
pal+=String.valueOf(val.charAt(j));
}
return val.equals(pal);
}