# My answer got accepted, but is this really plausibly an interview question?

• I am afraid there might be an easier way, because this is just too much for an interview question. And the odd length palindrome edge case is really tiresome! Here is my code:

``````    public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
char [] c = s.toCharArray();

List<String>[] byBeginIx = new List[c.length];

//Initialized the palendrome matrix
for(int i = 0; i < c.length; ++i){
List<String> len1Pals = new ArrayList<String>();
byBeginIx[i] = len1Pals;
}

//Find palendrome by length
int maxPalLength = (c.length) / 2;
for(int palLength = 1; palLength <= maxPalLength; ++palLength){
for(int i = 0; i <= c.length - palLength * 2; ++i) {
int oddOffset = 0;
do{
for(int l = 0; l < palLength; ++l) {
}

boolean isPal = true;
for(int l = palLength + oddOffset; l < oddOffset + 2*palLength; ++l) {
isPal &= (pal.remove(0).equals(c[i+l]));
if(!isPal)
break;
}
if(isPal){
}
++oddOffset;
} while(oddOffset < 2 && oddOffset+i+2*palLength <= c.length);
}

}

//Navigate partial solutions
ArrayList<ArrayList<String>> retVal = new ArrayList<ArrayList<String>>();

for(String startingAt0: byBeginIx[0]) {
ArrayList<String> candidate = new ArrayList<String>();

bfs(byBeginIx, startingAt0, 0, candidate, retVal);
}

return retVal;
}

void bfs(List<String>[] byBeginIx, String latestPal, int latestPalStartIx, ArrayList<String> candidate, ArrayList<ArrayList<String>> retVal) {
int startIx = latestPal.length() + latestPalStartIx;
if(startIx == byBeginIx.length) {
// cool, we made it to the end of the string
return;
} else if (startIx > byBeginIx.length) {
// Oops, over shot the string
return;
}

for(String oneMorePal: byBeginIx[startIx]) {
ArrayList<String> candidateClone = new ArrayList<String>(candidate);
bfs(byBeginIx, oneMorePal, startIx, candidateClone, retVal);
}
}
}``````

• I think it's perfectly plausible. You may not need to write out everything, but showing the algorithm is pretty easy to do in an interview session. For each palindrome at the start, get all splits for the remaining string, add first palindrome to each split, and return. Get splits on recursively smaller strings. Technically, it's O(n^3) and there's likely a faster way, but it's fast enough to pass and pretty simple as an algorithm.

``````public class Solution {
HashMap<String,Boolean> palindromes = new HashMap<String,Boolean>();
HashMap<String,ArrayList<ArrayList<String>>> dict;
public ArrayList<ArrayList<String>> partition(String s) {
dict = new HashMap<String,ArrayList<ArrayList<String>>>();
return partitionSub(s);
}
public ArrayList<ArrayList<String>> partitionSub(String s){
if(dict.containsKey(s)) // if already have the result,
return dict.get(s);     // return it, don't recalculate

ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
if(s.length()==0)
res.add(new ArrayList<String>());  //if s is empty, start a new list
else
for(int i=1;i<=s.length();i++){    //for each possible starting palidrome
String start = s.substring(0,i);
if(isPalindrome(start)){         //if not a palindrome, skip it
ArrayList<ArrayList<String>> part = partitionSub(s.substring(i));  //partition remaining string
for(ArrayList<String> sample : part){
}
}
}
dict.put(s,res);     //store result for future checks
return res;
}
//check if s is a palindrome, might be skippable in interviews
public boolean isPalindrome(String s){
if(palindromes.containsKey(s))
return (palindromes.get(s)).booleanValue();
int m=0;int n=s.length()-1;
while(m<n){
if(s.charAt(m++)!=s.charAt(n--)){
palindromes.put(s,new Boolean(false));
return false;
}
}
palindromes.put(s,new Boolean(true));
return true;
}
}``````

• Shouldn't it be called DFS?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.