My java DP solution


  • 0
    T

    the sub-problem structure is that if you chop off a palindrome word at the end, the final solution would just be that chopped off word plus each existing "paths" for the sub problem. so I use a DP solution table to record the solution of paths ending in the current index.

    public class Solution {
        public List<List<String>> partition(String s) {
            int m = s.length();
            final char []ss = s.toCharArray();
            List<List<String>> [] solutionsEnding = new ArrayList[m];
            
            for(int i=0;i<m;i++) {
                solutionsEnding[i] = new ArrayList<List<String>>();
                for(int j=i-1;j>=-1;j--) {
                    if (isPalindrome(ss, j+1, i)) {
                        if (j>=0)
                        
                        solutionsEnding[i].addAll( extend(solutionsEnding[j], new String(ss,j+1,i-j)) ); 
                        else {
                            final int jj = j;
                            final int ii =i;
                        solutionsEnding[i].add(new ArrayList<String>(){{add(new String(ss,jj+1,ii-jj));}}); 
                        }
                    }
                }
            }
            
            return solutionsEnding[m-1];
        }
        
        List<List<String>> extend(List<List<String>> previousLists, String newSection) {
            List<List<String>> result = new ArrayList<List<String>>();
            for(List<String> row: previousLists) {
                List<String> copy = new ArrayList<String>(row);
                copy.add(newSection);
                result.add(copy);
            }
            return result;
        }
        
        boolean isPalindrome(char ss[] , int start, int end) {
            for(int i=0;i< (end - start+1)/2;i++) {
                if ( ss[start+i] != ss[end-i]) return false;
            } 
            return true;
        }
    }

Log in to reply
 

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