Dynamic programming – Interleaved strings

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

$\color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}$

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card

$\color{green}{this question is very interesting, do not see regret! 😄 😄 😄 ~}$

What problem can I choose to do dynamic programming?

Counting 1.

• How many ways can I get to the bottom right corner
• How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

• The maximum numeric sum of the path from the upper left corner to the lower right corner
• Maximum ascending subsequence length

3. Seek existence

• Stone game, whether the first hand will win
• Can we pick k numbers such that the sum is sum

Leecode 97. Interleaved strings

Given three strings s1, s2 and s3, please help verify that S3 is interlaced with s1 and S2.

The interleaving of two strings s and t is defined and performed as follows, where each string is split into several non-empty substrings:

s = s1 + s2 + … + sn

t = t1 + t2 + … + tm

|n – m| <= 1

Interleaving is S1 + T1 + S2 + T2 + S3 + t3 +… Or T1 + S1 + T2 + S2 + t3 + S3 +…

Tip: A + b means the strings a and B are concatenated.

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadBBCBCAc”

Output: true,

Example 2:

Input: s1 = “aabcc”, s2 = “dbbCA “, s3 =” aadbbbACCc”

Output: false

Example 3:

Input: s1 = “”, s2 = “”, s3 = “”

Output: true,

—

Four steps for dynamic planning ~~~ ❤️❤️❤️❤️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

So we can draw a two-dimensional picture of something like this, for example: s1 = “aab” s2 = “bac” s3= “abacab”

And you can see, in two dimensions, that we have a path, and that path is exactly the intersection of S1 and S2.

Obviously, the last step is dp[I][j], and the coordinate point is 3,3.

subproblems

Is this similar to the different paths?

So if we want to form this path, we can say I minus one and j minus one, if we say si I minus one is on the path s3

Similarly, s2’s j-1 coordinates are exactly on the path s3

And it also has to be that the previous point is also on this path.

Color {yellow}{think I am very handsome ~} don’t think I am very handsome ❤️❤️❤️

2.2. Dynamic programming component 2: Transfer equation

I looked at the subproblem analysis, which is essentially the analysis of the left and the right.

The transfer equation is easy to write:

dp[i,j] = (dp[i-1][j] &&s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])

2.3. Dynamic programming component 3: Initial conditions and boundary cases

dp[0][0] = true

If I is equal to 0, let’s see if the left-hand side of j is on the path, and if j is equal to 0, let’s see if the left-hand side of I is on the path. Or I is greater than 0,j is greater than 0.

2.4. Dynamic programming component 4: Order of calculation

Each character of S1 traverses each character of S2

Reference code

The language version

 func isInterleave(s1 string, s2 string, s3 string) bool {
        n, m, t := len(s1), len(s2), len(s3)
        if(n + m) ! = t {return false
        }
         // Dynamically define a two-dimensional array
        f := make([] []bool, n + 1)
        for i := 0; i <= n; i++ {
            f[i] = make([]bool, m + 1)
        }
        f[0] [0] = true
        for i := 0; i <= n; i++ {
            for j := 0; j <= m; j++ {
                p := i + j - 1
                if i > 0 { // The previous point is on the path && the left or top point is also on the path.
                    f[i][j] = f[i][j] || (f[i- 1][j] && s1[i- 1] == s3[p])
                }
                if j > 0 {
                    f[i][j] = f[i][j] || (f[i][j- 1] && s2[j- 1] == s3[p])
                }
            }
        }
        return f[n][m]
    }



Copy the code

JAVA version

 
    public boolean isInterleave(String s1, String s2, String s3) {
            int m = s1.length(), n = s2.length();
            if(s3.length() ! = m + n)return false;
            // dynamic programming, dp[I,j] indicates that the I character before S1 and the j character before S2 can form the I + J character before S3;
            boolean[][] dp = new boolean[m+1][n+1];
            dp[0] [0] = true;
            for (int i = 1; i <= m && s1.charAt(i-1) == s3.charAt(i-1); i++) {
                dp[i][0] = true; 
            }
            for (int j = 1; j <= n && s2.charAt(j-1) == s3.charAt(j-1); j++) {
                dp[0][j] = true; 
            }
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = (dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1))
                            || (dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1)); }}return dp[m][n];
        }


    

Copy the code

❤ ️ ❤ ️ ❤ ️ ❤ ️

Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much!

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.