“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The interleaved string is shown below:

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
  • staggered 是 s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...

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

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbCAc" Output: trueCopy the code

A, thinking

** Determine whether substrings of s1 and substrings of S2 can form S3 **

Obviously the following conditions must be met:

  • s1.len + s2.len == s3.len:s1 和 s2The sum of the lengths of theta is going to be equal tos3The length of the
  • s1 和 s2The number of characters must be equal tos3Contains the same number of characters

We can assume that 1 ~ I in S1 can form an interlaced string with 1 ~ j in S2, as shown in the figure below:

Note: I and j here refer to positions (or numbers) of elements starting at 1, not subscripts in the array

If the I +j+1 element in s3 is c, which element can be added to s1 or s2?

  • s1 中 1 ~ i+1 和 s2In the1 ~jMake up interleaved strings3 (1 ~ i+j+1)
  • ors1 中 1 ~ i 和 s2In the1 ~j+1Make up interleaved strings3 (1 ~ i+j+1)?

The answer is obvious: either you call the end of S1 c or you add c to the end of s2, as shown in the picture below:

Through the above reasoning, we find that whether 1~ I characters of S1 and 1~ J characters of S2 form interlaced characters is related to whether their respective substrings 1~i-1 and 1~j, 1~ I and 1~ J-1 form interlaced characters. This is consistent with the idea of dynamic programming.

Assuming that dp[I][j] is whether 1~ I in S1 and 1~j in S2 form interleaving characters, we can easily obtain the state transition equation according to the above reasoning:

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

Now that I have the idea, implementing the code is a bottom-up process.

Second, the implementation

The implementation code

We’re going to initialize the boundary values before we iterate

    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        // If the length is not equal, it must not be an interleaved string
        if(len1 + len2 ! = len3)return false;
        boolean[][] dp = new boolean[len1+1][len2+1];
        // Initialize the boundary
        dp[0] [0] = true;
        // Initialize the first column and row
        for (int i=1; i<=len2; i++) {
            dp[0][i] = s2.charAt(i-1) == s3.charAt(i-1) && dp[0][i-1];
        }
        for (int i=1; i<=len1; i++) {
            dp[i][0] = s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1] [0];
        }
        // Fill dp according to the state transition equation
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) ||
                        (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)); }}return dp[len1][len2];
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number97().isInterleave("db"."b"."cbb");
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section