Java DP solution with explanation


  • 0

    Two DP in this problem:

    1. Use dp to find all palindrome string [i , j)
    2. Start from index i=1 until i=n, calculate all the partitions for sub-string [0, i)
    public List<List<String>> partition(String s) {
             int n=s.length();
             List<List<String>>[] palindromeList = new List[n+1];
             boolean[][] valid = new boolean[n+1][n+1];
             char[] arr = s.toCharArray();
             // O(n^2) to get all the palindromes index pairs
             check(arr, valid);
             
             // bottom up dp, i represents s.substring(0, i);
             for(int i=1;i<=arr.length;++i){
                List<List<String>> lists = new LinkedList<>();
                // corner case
                if(valid[0][i]) lists.add(Arrays.asList(s.substring(0,i)));
    
                // add new palindromes to previous lists
                for(int j=1; j<i; ++j){
                    if(!valid[j][i]) continue;
                    String cur = s.substring(j,i);
                    List<List<String>> subLists = palindromeList[j];
                    for(List<String> list: subLists){
                        List<String> copy = new ArrayList<>(list);
                        copy.add(cur);
                        lists.add(copy);
                    }
                }
                palindromeList[i]=lists;
            }
             return palindromeList[n];
        }
        
    
        private void check(char[] arr, boolean[][] valid){
            int n = arr.length;
            for(int i=1;i<n+1;++i){
                for(int j=0;j<i;++j){
                    if(i-j==1) valid[j][i]=true;
                    else if(i-j==2) valid[j][i]= arr[j]==arr[i-1];
                    else if(arr[j]==arr[i-1] && valid[j+1][i-1]){
                        valid[j][i]=true;
                    }
                }
            }
        }
    
    

Log in to reply
 

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