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

Topic describes

This is 132. Split palindrome string II on LeetCode, difficulty is difficult.

Tag: “palindrome string”, “linear DP”

Given a string s, please split s into substrings so that each substring is palindrome.

Returns the minimum number of splits that meet the requirement.

Example 1:

Input: s = "aab" Output: 1Copy the code

Example 2:

Input: s = "a" Output: 0Copy the code

Example 3:

Input: s = "ab" Output: 1Copy the code

Tip:

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

Dynamic programming solution

If you have used DP to preprocess the palindrome string in 131.

So this is a very simple problem, just a regular dynamic programming problem.

Recursive “minimum number of segmentation” idea

We define f[I] as the minimum number of splits ending with a character subscript I, so the final answer is F [n-1].

Without loss of generality consider the JTH character segmentation scheme:

  1. From the starting character to the firstjTo form a palindrome string, the minimum number of segmentation is 0. At this time there aref[j] = 0
  2. From the starting character to the firstjCannot form a palindrome string:
    1. This character consumes one split count independently. At this time there aref[j] = f[j - 1] + 1
    2. This character does not consume a split count independently, but with a previous positioniForm a palindrome string,[i, j]As a whole, it consumes a number of partitions. At this time there aref[j] = f[i - 1] + 1

There may be many positions I that meet palindrome requirements in 2.2, and we can just take a min in all schemes.

Quick judgment “any substring is palindrome” train of thought

The remaining question is, how can we quickly determine whether a continuous paragraph [I, j] is a palindrome string? The split palindrome string is exactly the same.

PS. In yesterday’s question, the data range is only 16, so we can use double Pointers instead of DP for preprocessing to judge whether palindromes can also pass. But the data range of this problem is 2000 (the order of magnitude is
1 0 3 10 ^ 3 ), using the naive method to determine whether palindromes or not, the complexity will go to
O ( n 3 ) O(n^3) (The computation quantity is
1 0 9 10 ^ 9 ), must time out.

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.

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 int minCut(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        St [I][j] indicates whether the interval [I,j] is a palindrome string
        boolean[][] st = 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) {
                    st[i][j] = true;
                } else {
                    // If [I, j] is 2, cs[I] == cs[j] is a palindrome string
                    if (j - i + 1= =2) {
                        st[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 {
                        st[i][j] = cs[i] == cs[j] && st[i + 1][j - 1]; }}}}// f(I) represents the minimum number of splits to consider ending characters with subscript I
        int[] f = new int[n]; 
        for (int j = 1; j < n; j++) {

            // If [0,j] is a palindrome, there is no need to split it
            if (st[0][j]) { 
                f[j] = 0;

            // If you cannot form a palindrome directly
            // For the JTH character, there is a choice between using split count or not using split count
            } else { 
                // The following two decisions can also be combined into a loop, but f[I] needs to be preset to a large enough number, so it can be done separately

                // Use a separate split count
                f[j] = f[j - 1] + 1;

                // The JTH character itself does not use the split count independently
                // represents to form the interval [I,j] with a previous position I, so that [I,j] forms a palindrome, and [I,j] consumes the whole number of segmentation
                for (int i = 1; i < j; i++) {
                    if (st[i][j]) {
                        f[j] = Math.min(f[j], f[i - 1] + 1); }}}}return f[n - 1]; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

How to determine the DP status definition

Some students will have doubts about “how to determine the state definition of DP” and feel that they can not always decide the state definition of DP.

First of all, it’s perfectly normal. Don’t worry.

The state definition of DP is basically empirical (guess), guess the state definition of DP, basically “state transition equation” is ready to come out.

While most of the cases are guessing, it’s not random, with a fair number of definitions having to do with “ends” and “answers.”

For example, f[I] is defined as the minimum number of splits (the answer) that end with a character subscript I.

So for those DP model problems you haven’t seen before, you can “guess” from these two aspects.

Manacher algorithm (non-important supplement)

If you still have enough spare time, you can look at the following problem solution.

Manacher algorithm is the ultimate answer to the “palindrome string” problem.

Since Manacher algorithm is limited and can only solve the problem of “palindrome string”, it is far less widely used than KMP algorithm. It is not recommended to study the principle deeply, but to recite it directly as a “template”.

The point of memorizing such an algorithm is that you have an O(n)O(n)O(n) O(n) API in your brain to use, which passes in a string and returns the largest substring of that string.

The ultimate answer to the palindrome string problem: Manacher algorithm

If you don’t think you can recite it, that’s fine. In fact, I’ve never seen a palindrome that had to use Manacher’s algorithm.

The last

This is No.132 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

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.