• Below is my DP solution, I failed on test:

``````Input:	  "aa", "ab"
Output:       true
Expected:   false
``````

I tested my solution on my local (C++ 4.2.1, Apple LLVM version 6.0) but didn't find any problem... Please help, thanks in advance!

Below is my code in C++:

``````    //DP
//f[i][j][k]: if s1[i..k] and s2[j..k] are scramble strings of each other
//init: f[i][j][1] is true if s1[i]==s[j], false otherwise
//goal: f[0][0][len+1]
//iteration: f[i][j][k] = f[i][j][k] || (f[i][j][p] && f[i+p][j+p][k-p]) || (f[i][j+k-p][p] && f[i+p][j][p])
bool isScramble(string s1, string s2) {
if(s1.size() != s2.size()){
return false;
}
if(s1 == s2){
return true;
}
int len = s1.size();
bool f[len][len][len+1];
//init
for(int i=0; i<len; i++){
for(int j=0; j<len; j++){
f[i][j][1] = (s1[i] == s2[j]);
}
}
//iteration
for(int k=2; k<=len; k++){   //current length
for(int i=0; i<=len-k; i++){
for(int j=0; j<=len-k; j++){
for(int p=1; p<k; p++){ //split position
f[i][j][k] |= (f[i][j][p] && f[i+p][j+p][k-p]) || (f[i][j+k-p][p] && f[i+p][j][p]);
}
}
}
}
return f[0][0][len];
}``````

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