I obtained the topic through the LEetcode plug-in of IDEA, so the topic description basically has the annotation symbol

When solving this set of problems, refer to one of the solutions of LeetCode, the link is as follows

Dynamic programming in interview: a series of segmented palindromes

1. Topic description

 * // [131] Separate palindrome strings
 * // Given a string s, split s into substrings such that each substring is a palindrome string.
 * //
 * // Return all possible split schemes for s.
 * //
 * / / sample:
 * //
 * // Enter: "aab"
 * / / output:
 * / / /
 * // ["aa","b"],
 * // ["a","a","b"]
 * / /]
 * // Related Topics backtracking algorithm
Copy the code

2. Analysis of ideas

So what this problem wants is all of the solutions, so for each of the solutions, the values in the List are palindromes.

According to the position of the first palindrome string, we divide the left and right strings as the first point of segmentation. The left string is added to the List of segmentation scheme, and then the right string is judged to cut the position of the first palindrome string.

The exit condition is that the length of the right string is 0, so it can’t be split. At this point, add the split scheme to the result set.

3. The AC code

public class No131 {

    public static List<List<String>> partition(String s) {
// return method1(s);
        return method2(s);
    }

    // ------ method1 start --------

    /** * Construct two lists * to receive the result of List<List<String>> re ** to receive the temp of each partition scheme ArrayList<String> ** execution time :11 ms, beating 62.28% of Java users * Memory consumption :51.3 MB, beating 87.81% of Java users * *@param s
     * @return* /
    private static List<List<String>> method1(String s) {
        List<List<String>> re = new ArrayList<List<String>>();
        traceBack(re,s,new ArrayList<String>());
        return re;
    }

    If the left string is a palindrome string, add it to the array temp, and then tracBack the right string **@param re
     * @param s
     * @param temp
     */
    private static void traceBack(List<List<String>> re, String s, ArrayList<String> temp) {
        if(s==null || s.length()==0) {
            re.add(new ArrayList<String>(temp));
        } else {
            for (int i = 1; i <= s.length(); i++) {
                // The judgment string used before
                if(isPalidrome(s.substring(0,i))) {
                    // Join if you are satisfied
                    temp.add(s.substring(0,i));
                    // System.out.println(s.substring(0,i))

                    // Notice that the string value passed here is s.substring(I)
                    // The first string has been cut out and added to the temp List
                    traceBack(re,s.substring(i),temp);
                    // The current List has been added to the result set, and the next loop is deleted one by one, i.e. s.substring (0, I +1).
                    temp.remove(temp.size()-1); }}}}/** * palindrome string judgment **@param s
     * @return* /
    private static boolean isPalidrome(String s) {
        int left = 0;
        int right = s.length()-1;

        while(left < right) {
            if(s.charAt(left) ! = s.charAt(right))return false;
            left++;
            right--;

        }

        return true;
    }

    // ------ method1 end --------
    // ------ method2 start --------

    To run the test, put res in method2 and add the res parameter to the DFS method
    public static List<List<String>> res = new ArrayList<>();


    /** * Method 2 is similar to method 1, but the difference is that it constructs a palindrome table to verify whether it is a palindrome ** execution time :8 ms, beating 91.72% of Java users ** memory consumption :52.4 MB, beating 47.78% of Java users */
    public static List<List<String>> method2(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                / / (j - I < 2 | | dp + 1] [I] [j - 1) no Spaces or contract before one is also a palindrome, from top to bottom, the fine product
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) dp[i][j] = true;
            }
        }
        dfs(s, 0, n, new ArrayList<>(), dp);
        return res;
    }

    private static void dfs(String s, int i, int n, List<String> sub, boolean[][] dp) {
        if (i == n) {
            res.add(new ArrayList<>(sub));
            return;
        }
        for (int j = i; j < n; j++) {
            if (dp[i][j]) {
                sub.add(s.substring(i, j + 1));
                dfs(s, j + 1, n, sub, dp);
                sub.remove(sub.size() - 1); }}}// ------ method2 end --------


    public static void main(String[] args) {
        String s = "aab"; System.out.println(partition(s)); }}Copy the code

4. To summarize

Method one is to think that you can write it, and method two is to think that you can’t write it without looking at the answer. To study the

It is obvious that method 2 takes less time than method 1 to construct a fast palindromic table. For today’s development, some of the more performance, you can slightly consider using more space to speed up the performance of the calculation. Trade space for time. That’s another idea.

We can’t just settle for something that we can do, and sometimes we can do something nicer that will help us write better code. Enrich yourself by learning from others’ strengths.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign