131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Classic Backtracking, list all possbile trails + backtrack when finishing or failing

// import java.util.*;
public class lt131 {
    public static List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> list = new ArrayList<String>();
        dfs(s, 0, list, res);
        return res;
    }

    public static void dfs(String s, int pos, List<String> list, List<List<String>> res) {
        if (pos == s.length())
            res.add(new ArrayList<String>(list));
        else {
            for (int i = pos; i < s.length(); i++) {
                if (isPal(s, pos, i)) {
                    list.add(s.substring(pos, i + 1));
                    dfs(s, i + 1, list, res);
                    list.remove(list.size() - 1);// backtrack when finishing or failing
                }
            }
        }
    }

    public static boolean isPal(String s, int low, int high) {
        while (low < high){
            if (s.charAt(low++) != s.charAt(high--)){
                return false;
            }
        }
        return true;
    }

    // *********************************************
    public static void main(String[] args) {
        String s = "aaa";
        for (List<String> ls : partition(s))
            System.out.println(ls);
    }
}

DP_1

public class lt131 {
    public static List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        //DP begin
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int pos = 0; pos <= i; pos++) {
                if (s.charAt(i) == s.charAt(pos) && (i - pos <= 2 || dp[pos + 1][i - 1])) {
                    dp[pos][i] = true;
                }
            }
        }//DP end 
        // for (boolean[] dp_row : dp)
        //     System.out.println(Arrays.toString(dp_row));
        helper(s, 0, res, new ArrayList<>(), dp);
        return res;
    }

    private static void helper(String s, int pos, List<List<String>> res, List<String> path, boolean[][] dp) {
        if (pos == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = pos; i < s.length(); i++) {
            if (dp[pos][i]) {
                path.add(s.substring(pos, i + 1));
                helper(s, i + 1, res, path, dp);
                path.remove(path.size() - 1);
            }
        }
    }

    // *********************************************
    public static void main(String[] args) {
        String s = "aabbaa";
        for (List<String> ls : partition(s))
            System.out.println(ls);
    }
}

DP_2
https://leetcode.com/problems/palindrome-partitioning/discuss/41974/My-Java-DP-only-solution-without-recursion.-O(n2)

public class lt131 {
    public static List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>>[] result = new List[len + 1];
        result[0] = new ArrayList<List<String>>();
        result[0].add(new ArrayList<String>());
        // System.out.println(Arrays.toString(result));
        boolean[][] pair = new boolean[len][len];
        for (int right = 0; right < s.length(); right++) {
            result[right + 1] = new ArrayList<List<String>>();
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 1 || pair[left + 1][right - 1])) {
                    pair[left][right] = true;
                    String suffix_sub = s.substring(left, right + 1);
                    // Check each suffix of the given string, if the suffix is a palindrome, add it
                    // to each solution for subproblem of the matching prefix, else skip it.
                    // result[0..right] = result[0..left-1] + s[left..right] if s[left..right]
                    // is a palindrome,
                    for (List<String> prev : result[left]) {
                        List<String> list = new ArrayList<String>(prev);
                        list.add(suffix_sub);
                        result[right + 1].add(list);
                    }
                }
            }
        }
        // for (List<List<String>> ls : result) System.out.println(ls);
        return result[result.length - 1];
    }
    // *********************************************
    public static void main(String[] args) {
        String s = "aabbaa";
        for (List<String> ls : partition(s))
            System.out.println(ls);
    }
}