扰乱字符串

力扣链接：87. 扰乱字符串

题目描述

使用下面描述的算法可以扰乱字符串 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
示例 2：

输入：s1 = “abcde”, s2 = “caebd”
输出：false
示例 3：

输入：s1 = “a”, s2 = “a”
输出：true

Java代码1（我能看懂的超时了！）

class Solution {public boolean isScramble(String s1, String s2) {if(s1.length() != s2.length()) return false;if(s1.equals(s2)) return true;int[] mem = new int[26];for(int i = 0; i < s1.length(); i++) {mem[s1.charAt(i) - 'a']++;mem[s2.charAt(i) - 'a']--;}for(int m : mem) {if(m != 0) return false;}for(int i = 1, len = s1.length(); i < len; i++) {if(isScramble(s1.substring(0, i), s2.substring(0, i)) &&isScramble(s1.substring(i), s2.substring(i))) {return true;}if(isScramble(s1.substring(0, i), s2.substring(len - i)) &&isScramble(s1.substring(i), s2.substring(0, len - i))) {return true;}}return false;}
}

Java代码2（还是不会啊这破题！）

class Solution {public boolean isScramble(String s1, String s2) {if (s1.equals(s2)) return true;if (s1.length() != s2.length()) return false;int n = s1.length();char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();boolean[][][] f = new boolean[n][n][n + 1];// 先处理长度为 1 的情况for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {f[i][j][1] = cs1[i] == cs2[j];}}// 再处理其余长度情况for (int len = 2; len <= n; len++) {for (int i = 0; i <= n - len; i++) {for (int j = 0; j <= n - len; j++) {for (int k = 1; k < len; k++) {boolean a = f[i][j][k] && f[i + k][j + k][len - k];boolean b = f[i][j + len - k][k] && f[i + k][j][len - k];if (a || b) {f[i][j][len] = true;}}}}}return f[0][0][n];}
}