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

preface

The disturbing string is as follows:

You can perturb string S to get string t using the algorithm described below:

  1. If the length of the string is 1, the algorithm stops

  2. If the string length is greater than 1, perform the following steps:

    • Splits a string into two non-empty substrings at a random subscript. That is, if you have a strings, you can split it into two substringsx 和 yAnd meets = x + y 。
    • randomDecide whether you want to “swap the two substrings” or “keep the order of the two substrings the same.” That is, after performing this step,sMay bes = x + yors = y + x 。
    • inx 和 yThe algorithm continues recursively from step 1 on these two substrings.

You are given two strings s1 and s2 of equal length, and determine if S2 is the perturb of S1. If so, return true; Otherwise, return false.

Example 1:

Input: s1 = "great", s2 = "rgeat" output: true Explanation: One situation that can occur on s1 is: "Great" --> "gr/eat" // Two substrings "gr/eat" --> "gr/eat" // randomly decide: "Keep the order of the two substrings unchanged" "gr/eat" --> "g/r /e /at" // Executes this algorithm recursively on the substring. Two substrings are split at random subscripts "g/r/e/at" --> "r/g/e/at" // randomly decide: "R /g/E /at" -->" R /g/e/a/T "// Continue recursively executing the algorithm, Use "at" split to get "a/t" "r/g/e/a/t" - > "r/g/e/a/t" / / random decision: "Keep these two substrings in the same order" algorithm terminates, resulting in the same string as S2, both "rgeat", which is a case where you can perturb S1 to get S2, you can think of S2 as a perturb of S1, return trueCopy the code

A, thinking

This problem should be the most difficult one I have written recently. I tried to write recursively at the beginning. Because recursion is the best answer, which is to keep reducing the size of the problem until you find the right answer.

However, the recursion failed to pass all the test cases because of the time complexity, and it ran out of time in the next few test cases. Let me outline the pseudo-code for recursion:

public boolean isScramble(String s1, String s2) { if (s1.length() ! = s2.length()) return false; If (s1.equals(s2)) // Return true if two strings are equal. // If s1 and s2 have different characters, return false if(! judgeCharacter(s1, s2)) return false; for (int i = 1; i < n; If (isScramble(s1.substring(0, I), s2.substring(0, 0)) {// If (isScramble(s1.substring(0, I), s2.substring(0, 0)) i)) && isScramble(s1.substring(i), s2.substring(i))) return true; if (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) return true; } return false; }Copy the code

Recursion is relatively easy to understand, just keep splitting and comparing the results of splitting or swapping strings. Returns true until the correct result can be found once

Later, I went to read the solution of the problem. The official solution was dynamic programming. At first, I could not understand the meaning of DP in the solution.

We use dp[I][j][k] to indicate whether a string of length k starting from I in string s1 can be transformed into a string of length k starting from 2 in string s2

Thus we can obtain a state transition equation:

dp[i][j][k] = dp[i][j][w] && dp[i+w][j+w][k-w] || dp[i][j+k-w][w] && dp[i+w][j][k-w]

W: indicates a constant, ranging from 1 < w < k dp[I][j+k-w][w] : indicates whether characters in s1[I, I +w] can be converted to S2 [j+k-w, k]

The advantage of this is that you can use the previous calculation to calculate the current value without having to repeat the calculation

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public boolean isScramble(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int n = s1.length();
        int m = s2.length();
        if(n ! = m) {return false;
        }
        boolean[][][] dp = new boolean[n][n][n + 1];
        // Initial boundary clearing: single character case
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = chars1[i] == chars2[j]; }}for (int len = 2; len <= n; len++) { // Intercepts the character length
            for (int i = 0; i <= n - len; i++) {    // the starting position of s1
                // Enumerate the starting position in T
                for (int j = 0; j <= n - len; j++) {    // the starting position of s2
                    // Enumerates the location
                    for (int k = 1; k <= len - 1; k++) {
                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0] [0][n];
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number87().isScramble("eebaacbcbcadaaedceaaacadccd"."eadcaacabaddaceacbceaabeccd");
    }
Copy the code

The results of

Third, summary

At the end of the article, thanks for the solution of the problem

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