Java: Easy to Understand DP+Backtracking (7ms)


  • 0

    First compute and store the palindromes start from each position. Time: O(N^2)

    Then use this information to decide the possible next step start positions in backtracking.

    Time complexity: there is no way to do better than O(2^N) in worst case, since for "aaaaaaaaaaaaa" there will be ~2^N different partitions.
    However, since we only need to test each possible palindrome once in this solution, I would say this should be a fast solution.

    public class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> res=new ArrayList<>();
            if(s==null||s.length()==0) return res;
            /*Compute the palindroms start from each position*/
            ArrayList<String>[] pals=new ArrayList[s.length()]; //the palindromes start from index i.
            for(int i=0; i<pals.length; i++) pals[i]=new ArrayList<String>();
            char[] chars=s.toCharArray();
            int len=s.length();
            for(int i=0; i<len-1; i++){
                /*odd length*/
                int left=i, right=i;
                while(left>=0 && right<len && chars[left]==chars[right]){
                    pals[left].add(s.substring(left, right+1));
                    left--;
                    right++;
                }
                /*even length*/
                left=i; right=i+1;
                while(left>=0 && right<len && chars[left]==chars[right]){
                    pals[left].add(s.substring(left, right+1));
                    left--;
                    right++;
                }
            }
            pals[len-1].add(s.substring(len-1, len)); //Add the last char
            List<String> partition=new ArrayList<>();
            partition(chars, 0, partition, res, pals);
            return res;
        }
        
        private void partition(char[] chars, int start, List<String> partition, List<List<String>> res, List<String>[] pals){
            if(start==chars.length){
                res.add(new ArrayList(partition));
                return;
            }
            List<String> set=pals[start];
            for(String str: set){
                partition.add(str);
                partition(chars, start+str.length(), partition, res, pals);
                partition.remove(partition.size()-1);
            }
        }
    }
    

Log in to reply
 

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