Split palindrome string [dp + DFS combination]

Preface

Dynamic programming , Space for time , For example, whether a string is a palindrome , See whether the middle part is palindrome and whether the two ends are equal .
DFS Find combination , Classic backtracking scenes .

One 、 Split palindrome string

Two 、 Preprocessing DP + DFS Combine

package everyday.dp;

import java.util.ArrayList;
import java.util.List;

//  Split palindrome string 
public class Partition {
    
    /* target： The outer goals ： Get palindrome combination , can DFS, But the inner layer needs to know that the interval is palindrome , Ability palindrome combination , therefore   Whether the preprocessing is a palindrome  + DFS Are combined . */
    public List<List<String>> partition(String s) {
    
        //  Preprocess whether various strings are palindromes .
        boolean[][] f = preProcess(s);
        // dfs Combine 
        List<List<String>> ans = new ArrayList<>();
        List<String> el = new ArrayList<>();
        dfs(s, 0, el, ans, f);
        //  Return the processed combination .
        return ans;
    }

    // DFS  Combine all possible palindrome strings .
    private void dfs(String s, int cur, List<String> el, List<List<String>> ans, boolean[][] f) {
    
        if (cur == s.length()) {
    
            //  The legal end , Not only does recursion end , And put the legal combination into ans
            ans.add(new ArrayList<>(el));
            return;
        }
        //  Standard backtracking 
        for (int i = cur; i < s.length(); i++) {
    
            if (f[cur][i]) {
    
                el.add(s.substring(cur, i + 1));
                dfs(s, i + 1, el, ans, f);
                el.remove(el.size() - 1);
            }
        }
        //  There is no legal combination to reach the end . no need ans.add, And end recursion .
    }

    //  Decision interval [i,j] Is it palindrome .
    private boolean[][] preProcess(String s) {
    
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        for (int j = 0; j < n; j++) {
    
            //  Every single letter is a palindrome .
            f[j][j] = true;
            for (int i = j - 1; i >= 0; i--) {
    
                // f[i][j]  Is it a palindrome , Want to see s[i] == s[j]  And f[i - 1][j - 1] It's palindrome. .
                if (s.charAt(i) != s.charAt(j)) continue;
                if (i + 1 == j || f[i + 1][j - 1]) f[i][j] = true;
            }
        }
        return f;
    }

    public static void main(String[] args) {
    
        new Partition().partition("aab");
    }
}

summary

1） Clear understanding , What does the outer layer need , Want to put up an outer layer , What inner layer is needed . From the outside to the inside , Solve the subproblem from the inside out .
2） Dynamic programming /DFS Combine .

reference

[1] LeetCode Split palindrome string