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


  • 0
    Y

    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>();
                len1Pals.add(c[i] + "");
                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{
                        LinkedList<Character> pal = new LinkedList<Character>();
                        for(int l = 0; l < palLength; ++l) {
                            pal.add(0,c[i+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){
                           byBeginIx[i].add(s.substring(i,i+oddOffset+2*palLength)); 
                        }
                        ++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>();
                
                candidate.add(startingAt0);
                
                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
                retVal.add(candidate);
                return;
            } else if (startIx > byBeginIx.length) { 
                // Oops, over shot the string
                return;
            }
            
            for(String oneMorePal: byBeginIx[startIx]) {
                ArrayList<String> candidateClone = new ArrayList<String>(candidate);
                candidateClone.add(oneMorePal);
                bfs(byBeginIx, oneMorePal, startIx, candidateClone, retVal); 
            }
        }
    }

  • 7
    M

    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){
                ArrayList<String> added = new ArrayList<String>(sample);
                added.add(0,start);   //add starting palindrome to each partial solution
                res.add(added);
              }
            }
          }
          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;
      }
    }

  • 0
    C

    Shouldn't it be called DFS?


Log in to reply
 

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