This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 131 on LeetCode. Split palindrome string, medium difficulty.

Tag: “Palindrome string”, “backtracking algorithm”, “dynamic programming”

Given a string s, please split s into substrings so that each substring is a palindrome string. Returns all possible segmentation schemes for S.

A palindrome string is a string that is read forward and backward identically.

Example 1:

Input: s = "aab" output: [["a","a","b"] [" AA ","b"]Copy the code

Example 2:

Input: s = "a" output: [["a"]]Copy the code

Tip:

  • 1 <= s.length <= 16
  • The “S” is a lowercase letter only

Dynamic programming + backtracking algorithm

Ask for all the segmentation scheme, generally ask for all the project basically have no optimization scheme, is “explosion search”.

The question is, what? Apparently, we can search the beginning of every palindrome. If one of the consecutive paragraphs is a palindrome string, we continue to search the remaining consecutive paragraphs.

Why can we just pick up where we left off?

Because any substring must eventually be divided into several palindromes (in the worst case, each palindrome is a letter).

So every time we go down, all we need to do is make sure it’s a palindrome.

Take šŸŒ° to get a feel for our search process. Let’s say we have an example, Abababa. At the beginning, we start our search from the first a:

  1. foundaIt’s a palindrome stringaDivide it up and do the restbababaFor blast search
  2. foundabaIt’s a palindrome stringabaDivide it up and do the restbabaFor blast search
  3. foundababaIt’s a palindrome stringababaDivide it up and do the restbaFor blast search
  4. foundabababaIt’s a palindrome stringabababaSplit out, and then the rest of the search

.

And then the next starting point (the next character) b, right?

Don’t need.

Since a single character itself constitutes a palindrome string, the scheme to form a palindrome string before B, as the starting point, must be covered in the detonation search scheme that we expand with the first character as the starting point (in this case, it corresponds to the detonation search scheme launched in the first step above).

So we just need to start with the first character, enumerate all the palindromes that start with it, add them to the collection, and continue searching the rest of the string. Can do with any character as a palindrome string starting point for the effect of segmentation.

Be sure to understand the above sentence

The remaining question is, how can we quickly determine whether a continuous segment [I, j] is a palindrome string, because every position in the explosion search process can be used as a segmentation point, the complexity is O(2n)O(2^n)O(2n).

Therefore, it is impossible for us to use the double pointer to scan linear [I, j] every time to determine whether palindrome.

An intuitive way to do this is to preprocess all f[I][j], f[I][j] represents whether [I, j] is a palindrome string.

The process of preprocessing f[I][J] can be done recursively.

For f[I][j] == true, two conditions must be met:

  1. f[i + 1][j - 1] == true
  2. s[i] == s[j]

Since state F [I][j] depends on state F [I + 1][J-1], we need to traverse the left endpoint I from large to small. And the right endpoint j is going from small to large.

Therefore, our traversal process can be arranged as follows: the right endpoint J keeps moving to the right (from small to large); in the case that J is fixed, the left endpoint I starts at the left of J and keeps moving to the left (from large to small).

Code:

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // f[I][j] indicates whether [I, j] is a palindrome string
        boolean[][] f = new boolean[n][n];
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                // when [I, j] has only one character, it must be a palindrome string
                if (i == j) {
                    f[i][j] = true;
                } else {
                    // If [I, j] is 2, cs[I] == cs[j] is a palindrome string
                    if (j - i + 1= =2) {
                        f[i][j] = cs[i] == cs[j];

                    / / when [I, j] length is greater than 2, meet (cs = = cs [j] [I] && f + 1] [I] [j - 1) the palindrome string
                    } else {
                        f[i][j] = cs[i] == cs[j] && f[i + 1][j - 1];
                    }
                }
            }
        }
        List<List<String>> ans = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        dfs(s, 0, ans, cur, f);
        return ans;
    }
    /** * s: the string to search for * u: the bit in s as the starting point for the palindrome string split * ans: the final result set * cur: the current result set * f: quickly determine whether [I,j] is a palindrome string */
    void dfs(String s, int u, List<List<String>> ans, List<String> cur, boolean[][] f) {
        int n = s.length();
        if (u == n) ans.add(new ArrayList<>(cur));
        for (int i = u; i < n; i++) {
            if (f[u][i]) {
                cur.add(s.substring(u, i + 1));
                dfs(s, i + 1, ans, cur, f);
                cur.remove(cur.size() - 1); }}}}Copy the code
  • Time complexity: the complexity of dynamic programming preprocessing is O(n2)O(n^2)O(n2). In the explosive search process, each character can be used as a segmentation point, and there are two options: splitting or not splitting. The number of schemes is 2N āˆ’12^{n-1} 2N āˆ’1. Each character needs to be checked for splitting the remaining characters later, and the complexity is O(n)O(n)O(n) O(n)O(n). The overall complexity is O(nāˆ—2n)O(n * 2^n)O(nāˆ—2n)
  • Space complexity: the complexity of dynamic programming is
    O ( n 2 ) O(n^2)     ; The maximum number of schemes is
    2 n – 1 2^{n – 1}     , each scheme is a full strings, and the complexity is
    O ( n ) O(n)     , the overall complexity is
    O ( n āˆ— 2 n ) O(n * 2^n)

conclusion

For such a problem that enumerates all schemes, we should first think of “backtracking algorithms”.

“Backtracking algorithm” from the definition of the algorithm, does not necessarily use DFS implementation, but usually combined with DFS, is the least difficult.

The backtracking algorithm corresponds to two sets of templates based on how many choices there are in the current decision.

Each independent decision corresponds to only two cases of select and not select:

  1. Identify the base case that ends the backtracking process

  2. Traverse each location, making a decision on each location (make selection -> recurse -> Undo selection)

void dfs(Current location, path (current result), result set){
    if(Current position == end position) {result set.add (path);return; } Select the current position; DFS (next location, path (current result), result set); Unselect current location; DFS (next location, path (current result), result set); }Copy the code

Each individual decision corresponds to multiple choices (usually corresponding to what can be chosen per decision, or how many can be chosen per decision…). :

  1. Identify the base case that ends the backtracking process

  2. Go through all the “choices”

  3. Make a decision on the selection (make the selection -> recurse -> Undo the selection)

void dfsSelect list, path (current result), result set){
    if{result set. Add (path);return;
    }
        
    for(Select in select list) {make a selection; DFS (path ', selection list, result set); Undo selection; }}Copy the code

expand

Just recently update the “backtracking algorithm” related questions, the following questions can deepen your understanding of “backtracking” algorithm and the use of templates:

17. Alphabetic combinations of phone numbers (medium) : Share the basics of backtracking algorithms with you from a classic question on “backtracking algorithms”

39. Combined sum (medium) : DFS + backtracking algorithm and how to determine if a problem should be solved using DFS + backtracking

40. Combination Sum II(Medium) : [Backtracking algorithm] Combination Scheme for finding sum of objectives (Upgrade)

216. Sum of combinations III(medium) : [Backtracking algorithm] Summarize the backtracking algorithm with the help of the last “sum of combinations” problem

37. Solving Sudoku (difficult) : [Sudoku questions] Classic interview questions: Solving sudoku

The last

This is the No.131 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01, and there are 1916 questions on LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.