Java DP solution using tree


  • 0
    J
    public List<List<String>> partition(String s) {
            if (s == null || s.isEmpty()) return new ArrayList<>();
            List<List<Integer>> partitions = new ArrayList<>(s.length());
            for (int i = 0; i < s.length(); i++) {
                List<Integer> cs = new ArrayList<Integer>();
                partitions.add(cs);
                for (int j = 0; j <= i; j++) if (isPalindrome(s, j, i)) cs.add(j - 1);
            }
            return construct(s, partitions, s.length() - 1);
        }
        
        List<List<String>> construct(String s, List<List<Integer>> partitions, int root) {
            List<List<String>> result = new ArrayList<>();
            if (root == -1) result.add(new ArrayList<>()); 
            else {
                for (int child : partitions.get(root)) {
                    String surfix = s.substring(child + 1, root + 1);
                    List<List<String>> subPs = construct(s, partitions, child);
                    for (List<String> sl : subPs) {
                        List<String> nl = new ArrayList<>();
                        nl.addAll(sl);
                        nl.add(surfix);
                        result.add(nl);
                    }
                }
            }
            return result;
        }
        
        private boolean isPalindrome(String cs, int start, int end) {
            while (start < end) {
                if (cs.charAt(start) != cs.charAt(end)) return false;
                start++; end--;
            }
            return true;
        }
    

Log in to reply
 

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