This is the 24th day of my participation in Gwen Challenge

Topic describes

This is “131. Split Palindrome string” on LeetCode, with “medium” difficulty.

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. When a is found to be a palindrome string, first divide a and then search the remaining bababa

  2. Aba was found to be a palindrome string. Aba was first separated and then the remaining BABA was searched

  3. It is found that ABaba is a palindrome string. First, divide ABaba and then search the remaining BA

  4. It is found that abababa is a palindrome string. First, divide abababa and then search the rest

    .

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 problem is how to quickly judge whether a continuous paragraph is a palindrome string, because each position can be used as a segmentation point in the explosion search process, and the complexity is.

Therefore, it is impossible for us to use the double pointer to scan the line for palindromes every time.

An intuitive way to do this is to preprocess all of these to indicate whether the segment is a palindrome string.

The preprocessing process can be done recursively.

To do so, the following two conditions must be met:

Since the state depends on the state, the left endpoint is ** “from large to small” for traversal; The right endpoint is “from small to large” ** traverses.

Therefore, our traversal process can be arranged as follows: the right endpoint keeps moving to the right (from small to large); in the fixed case, the left endpoint starts at the left 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(); Boolean [][] f = new Boolean [n][n]; for (int j = 0; j < n; j++) { for (int i = j; i >= 0; I -) {/ / when [I, j] only one character is necessarily palindrome string if (I = = j) {f [I] [j] = true; } else {/ / when [I, j] of length 2, meet the cs = = cs [j] [I] the palindrome string if (j - I + 1 = = 2) {f [I] [j] [I] = = = cs 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] [I] = = = cs cs [j] && f [I + 1] [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 of the palindrome string * ans: the final result set * cur: the current result set * f: */ 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; In the explosion search process, each character can be used as a segmentation point, and there are two options: segmentation and non-segmentation. The number of schemes is, and each character needs to check the segmentation of the remaining characters later, and the complexity is. The overall complexity is

  • Spatial complexity: the complexity of dynamic programming is; The maximum number of schemes is, each scheme is the segmentation of the complete string S, the complexity is, and the overall complexity is

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 position, 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 DFS (select list, path (current result), result set) {if (end condition satisfied) {result set.add (path); return; } for (select in select list) {make a selection; DFS (path ', selection list, result set); Undo selection; }}Copy the code

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.