Problem Description
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Solution
Start forming substrings starting from index 0 to say index i. If that is a palindome, then recursively check for substring starting from index i to j. Keep doing this until all the characters have been considered in the input string. At that point, we have got one possible answer, so we can add that to the answer list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public List<List<String>> partition(String s) {
partitionHelper(s, 0, new ArrayList<>());
return ans;
}
List<List<String>> ans = new ArrayList<>();
public void partitionHelper(String s, int idx, List<String> list){
//idx is tracking the index from where we need to start the next substring
//if it's equal to the length of input string s, we have considered all the characters
//at this point, all the previos substrings considered were palindomes, we we can add it to answer list and return
if(idx >= s.length()){
ans.add(new ArrayList<>(list));
return;
}
//start from idx index and keep taking substrings with length 1, 2, 3 ...
//if the substring formed is a palindrome, start looking at next possible substring recursively
for(int i=idx; i<s.length(); i++){
//current substring
String sub = s.substring(idx, i+1);
//if it's a palindrome
if(isPalindrome(sub)){
//add it to the list
list.add(sub);
//recursively check for other palindrome substring
//IMPORTANT: we start looking for the current index we are currently at
partitionHelper(s, i+1, list);
//backtrack: remove the last substring which was added
list.remove(list.size()-1);
}
}
}
//this can be further optimized by taking two pointers at the start and end
public boolean isPalindrome(String s1){
StringBuilder s2 = new StringBuilder(s1);
s2.reverse();
if(s1.equals(s2.toString())) return true;
return false;
}
}