# AC Java Solution using Dynamic Programming (or Memorial Search)

• This is supposed to be an optimization of the simple solutions in the discussion board, because I'm using dynamic programming to store calculated states. But somehow it's actually slower. I guess it is because of the test cases.

For the DP matrix "scramble", scramble[i][j][k] means the substring of 's1' start at 'i' with length 'k' and the substring of 's2' start at 'j' with length'k' is scramble.

``````public boolean isScramble(String s1, String s2) {
boolean[][][] scramble = new boolean[s1.length() + 1][s1.length() + 1][s1.length() + 1];
boolean[][][] visited = new boolean[s1.length() + 1][s1.length() + 1][s1.length() + 1];
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
scramble[i][j][1] = s1.charAt(i) == s2.charAt(j);
visited[i][j][1] = true;
}
}
return isScramble(s1, s2, 0, 0, s1.length(), scramble, visited);
}

public boolean isScramble(String s1, String s2, int i1, int i2, int len, boolean[][][] scramble, boolean[][][] visited) {
if (visited[i1][i2][len]) return scramble[i1][i2][len];
visited[i1][i2][len] = true;

if (s1.equals(s2)) {
scramble[i1][i2][len] = true;
return true;
}

boolean result = false;
for (int i = 1; i < s1.length(); i++) {
String s11 = s1.substring(0, i);
String s12 = s1.substring(i, s1.length());
String s21 = s2.substring(s1.length() - i, s1.length());
String s22 = s2.substring(0, s1.length() - i);
String s23 = s2.substring(0, i);
String s24 = s2.substring(i, s1.length());
if ((isScramble(s11, s21, i1, i2 + s1.length() - i, i, scramble, visited) && isScramble(s12, s22, i1 + i, i2, s1.length() - i, scramble, visited)) ||
(isScramble(s11, s23, i1, i2, i, scramble, visited) && isScramble(s12, s24, i1 + i, i2 + i, s1.length() - i, scramble, visited))) {
scramble[i1][i2][len] = true;
return true;
}
}

scramble[i1][i2][len] = false;
return false;
}
``````

• Hi I found my DP solution is slower too! I also though it's because of the test case since
I ran few of the test cases and found only few of the functions get into check DP result.

• This post is deleted!

• @mancx111 Cool! Glad to hear someone shares similar ideas! Thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.