This is the 28th day of my participation in the August Text Challenge.More challenges in August
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 codeExample 2:
Input: s1 = "abcde", s2 = "caebd" Output: falseCopy the codeExample 3:
Input: s1 = "a", s2 = "a" output: trueCopy the codeTip:
S1. length == s2.length 1 <= s1.length <= 30 S1 and S2 consist of lowercase lettersCopy the codecode
var isScramble = function(s1, s2) { const length = s1.length; memo = new Array(length).fill(0).map(() => new Array(length).fill(0).map(() => new Array(length + 1).fill(0))); return dfs(0, 0, length, s1, s2, memo); }; const dfs = function(i1, i2, length, s1, s2, memo) { if (memo[i1][i2][length] ! == 0) { return memo[i1][i2][length] === 1; If (s1.slice(i1, i2 + length) === s2.slice(i2, i2 + length)) {memo[i1][i2][length] = 1; return true; } // Check if there are different occurrences of the character c in two substrings. checkIfSimilar(i1, i2, length, s1, s2)) { memo[i1][i2][length] = -1; return false; } for (let I = 1; i < length; If (DFS (i1, i2, I, s1, s2, memo) &&dfs (i1 + I, i2 + I, length -i, s1, s2, memo)) { memo[i1][i2][length] = 1; return true; } if (DFS (i1, i2 + leng-i, I, s1, s2, memo) && DFS (i1 + I, i2, leng-i, s1, s2, memo) && DFS (i1 + I, i2, leng-i, s1, s2, memo)) { memo[i1][i2][length] = 1; return true; } } memo[i1][i2][length] = -1; return false; } const checkIfSimilar = function(i1, i2, length, s1, s2) { const freq = new Map(); for (let i = i1; i < i1 + length; ++i) { const c = s1[i]; freq.set(c, (freq.get(c) || 0) + 1); } for (let i = i2; i < i2 + length; ++i) { const c = s2[i]; freq.set(c, (freq.get(c) || 0) - 1); } for (const value of freq.values()) { if (value ! == 0) { return false; } } return true; }Copy the code