I. Title Description:

Leetcode-cn.com/problems/sc… If the length of the string is greater than 1, perform the following steps: Split the string into two non-empty substrings at a random subscript. That is, if we know the string S, we can split it into two substrings x and y, such that s = x + y. Decide randomly whether you want to “swap two substrings” or “keep them in the same order.” That is, after this step, s could be either S = x + y or S = y + x. Continue recursively from Step 1 on the two substrings x and y. 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

Ii. Analysis of Ideas:

DFS + mnemonic search + Pruning method 1:

  • Find all the disturbing strings of S1, place them in the set, and determine whether S2 is in the set.
  • The recursive function is defined to return all perturbing strings of the string S

Method 2:

  • The recursive function is defined as whether S1 and s2 are perturbs, slicing the string, and then recursively determining whether the string is perturbs
  • The loop string sets I to the cut point, isScramble(s1,s2) = dfs(s1[0,i], s2[0,i]) && dfs(s1[i,n], s2[i,n]) || dfs(s1[0-i], s2[n-i,n]) && dfs(s1[i,n], s2[0,n-i])

Iii. AC Code:

/ * * *@param {string} s1
 * @param {string} s2
 * @return {boolean}* /
var isScramble = function (s1, s2) {
    const map = {}
    function strDfs(str) {
        const res = new Set(a)if(! str) {return res
        }
        if (str.length === 1) {
            return res.add(str)
        }
        if(map[str] ! = =undefined) {
            return map[str]
        }

        for (let i = 1; i < str.length; i++) {
            const substr1 = str.substring(i)
            const substr2 = str.substring(0, i)
            const strs1Arr = strDfs(substr1)
            const strs2Arr = strDfs(substr2)
            strs2Arr.forEach(str1= > {
                strs1Arr.forEach(str2= > {
                    const combineStr1 = str1 + str2
                    if(s2.indexOf(combineStr1) ! = = -1) {
                        res.add(combineStr1)
                    }
                    const combineStr2 = str2 + str1
                    if(s2.indexOf(combineStr2) ! = = -1) {
                        res.add(combineStr2)
                    }
                })
            })
        }
        map[str] = res
        return res
    }
    return strDfs(s1).has(s2)
};
Copy the code
/ * * *@param {string} s1
 * @param {string} s2
 * @return {boolean}* /
var isScramble = function (s1, s2) {
    const map = {}
    function dfs(a, b) {
        if(a.length ! == b.length) {return false
        }
        if (a.length === 1) {
            return a === b
        }
        if(map[a+b]! = =undefined) {return map[a+b]
        }
        for (let i = 1; i < a.length; i++) {
            const subAstr1 = a.substring(0, i)
            const subAstr2 = a.substring(i)
            const subBstr1 = b.substring(0, i)
            const subBstr2 = b.substring(i)
            const subBstr3 = b.substring(0, a.length - i)
            const subBstr4 = b.substring(a.length - i)
            if (dfs(subAstr1, subBstr1) && dfs(subAstr2, subBstr2)) {
                map[a+b] = true
                return true
            } else if (dfs(subAstr1, subBstr4) && dfs(subAstr2, subBstr3)) {
                map[a+b] = true
                return true
            }
        }
        map[a+b] = false
        return false
    }
    return dfs(s1, s2)
};
Copy the code