代码1
f[i][j][k] 表示 s1的 i 到 i + k 子字符是不是与 s2 的 j 到 j + k 的子字符符合。
Runtime: Runtime: 6 ms, faster than 39.75% of Java online submissions for Scramble String.
class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int len = s1.length();
boolean[][][] f = new boolean[len][len][len + 1];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (s1.charAt(i) == s2.charAt(j)) f[i][j][1] = true;
}
}
for (int k = 2; k <= len; k++) {
for (int i = 0; i + k <= len; i++) {
for (int j = 0; j + k <= len; j++) {
for (int q = 1; q < k; q++) {
if (f[i][j][q] && f[i + q][j + q][k - q]) {
f[i][j][k] = true;
break;
}
if (f[i][j + k - q][q] && f[i + q][j][k - q]) {
f[i][j][k] = true;
break;
}
}
}
}
}
return f[0][0][len];
}
}
