LeetCode面试题：扰乱字符串

　　1.简述：

　　使用下面描述的算法会扰乱字符串 s 得到字符串 t ：

　　假如字符串的长度是 1 ，算法停止

　　假如字符串的长度 > 1 ，执行以下步骤：

　　将字符串随机下标处分成两个非空子字符串。也就是说，如果已知字符串 s ，可分为两个子字符串 x 和 y ，且满足 s = x + y 。

　　随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。也就是说，执行此步骤后，s 可能是 s = x + y 或者 s = y + x 。

　　在 x 和 y 继续这两个子字符串的步骤 1 开始递归执行此算法。

　　给你两个 长度相等 的字符串 s1 还有s2，判断s2是否是s1的扰乱字符串。如果是，返回 true ;否则，返回 false 。

　　示例 1：

　　输入：s1 = "great", s2 = "rgeat"

　　输出：true

　　解释：s1 上述可能发生的情况之一是：

　　"great" --> "gr/eat" // 随机下标处分割两个子字符串

　　"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」

　　"gr/eat" --> "g/r / e/at" // 该算法在子字符串上递归执行。两个子字符串分别在随机下标处进行一轮分割。

　　"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」

　　"r/g / e/at" --> "r/g / e/ a/t" // 该算法将继续递归执行，并将继续递归执行 "at" 分割得到 "a/t"

　　"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」

　　算法终止，字符串和 s2 相同，都是 "rgeat"

　　这是一种干扰 s1 得到 s2 情况，可以认为 s2 是 s1 扰乱字符串，返回 true

　　示例 2：

　　输入：s1 = "abcde", s2 = "caebd"

　　输出：false

　　示例 3：

　　输入：s1 = "a", s2 = "a"

　　输出：true

　　2.实现代码：class Solution { // 记忆搜索存储状态的数组 // -1 表示 false，1 表示 true，0 表示未计算 int[][][][][][][][][] memo; String s1, s2; public boolean isScramble(String s1, String s2) { int length = s1.length(); this.memo = new int[length][length][length + 1]; this.s1 = s1; this.s2 = s2; return dfs(0, 0, length); } // 第一个字符串从 i1 从第二个字符串开始 i2 起初，子串的长度为 length，是否和谐 public boolean dfs(int i1, int i2, int length) { if (memo[i1][i2][i2][length] != 0) { return memo[i1][i2][i2][length] == 1; } // 判断两个子串是否相等 if (s1.substring(i1, i1 + length).equals(s2.substring(i2, i2 + length))) { memo[i1][i2][i2][length] = 1; return true; } // 判断字符是否存在 c 出现在两个子串中的次数不同 if (!checkIfSimilar(i1, i2, length)) { memo[i1][i2][i2][length] = -1; return false; } // 枚举分割位置 for (int i = 1; i < length; ++i) { // 不交换 if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) { memo[i1][i2][i2][length] = 1; return true; } // 交换的情况 if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) { memo[i1][i2][i2][i2][length] = 1; return true; } } memo[i1][i2][i2][i2][length] = -1; return false; } public boolean checkIfSimilar(int i1, int i2, int length) { Map freq = new HashMap(); for (int i = i1; i < i1 + length; ++i) { char c = s1.charAt(i); freq.put(c, freq.getOrDefault(c, 0) + 1); } for (int i = i2; i < i2 + length; ++i) { char c = s2.charAt(i); freq.put(c, freq.getOrDefault(c, 0) - 1); } for (Map.Entry entry : freq.entrySet()) { int value = entry.getValue(); if (value != 0) { return false; } } return true; }}