Simply we can just use recursive method to traverse every possible situations but as we can expect that we will run into TLE.

There are other factors we should make full use of to reduce the traversing range

- the limited characters
- the scrambled string is containing just exactly the same set of characters as the original string

which can be used to `prune`

almost all invalid traversing branches and result in the best time cost.

```
#define SIZE 256
bool isnScramble(char* s1, char* s2, int len)
{
if(!strncmp(s1, s2, len)) return true;
int count[SIZE] = {0};
for(int i = 0; i < len; i++)
count[s1[i]-'a']++, count[s2[i]-'a']--;
for(int i = 0; i < SIZE; i++)
if(count[i]) return false;
for(int i=1; i < len; i++)
if(isnScramble(s1, s2, i) && isnScramble(s1+i, s2+i, len-i) ||
isnScramble(s1, s2+len-i, i) && isnScramble(s1+i, s2, len-i)) return true;
return false;
}
//AC - 0ms - beats 100% submissions;
bool isScramble(char* s1, char* s2)
{
int len = strlen(s1);
return isnScramble(s1, s2, len);
}
```

A DP solution is also provided here with 20ms time cost, which is inspired by the above recursive method using three-dimension array to store the state

match[size][index1][index2]

the size is the comparing size of the two strings, index1 is the start index of string 1 and index2 is that of string 2.

```
//AC - 20ms - beats 100% submissions - DP solution;
bool isScramble(char* s1, char* s2)
{
int len = strlen(s1);
if(!len) return true;
if(len==1) return *s1==*s2;
bool*** match = (bool***)malloc(sizeof(bool**)*(len+1));
for(int i = 0; i <= len; i++)
{
match[i] = (bool**)malloc(sizeof(bool*)*len);
for(int j = 0; j < len; j++)
{
match[i][j] = (bool*)malloc(sizeof(bool)*len);
memset(match[i][j], 0, sizeof(bool)*len);
}
}
for(int i = 0; i < len; i++)
for(int j = 0; j < len; j++)
match[1][i][j] = (s1[i] == s2[j]);
for(int size = 2; size <= len; size++)
for(int i = 0; i <= len-size; i++)
for(int j = 0; j <= len-size; j++)
for(int k = 1; k<size && !match[size][i][j]; k++)
match[size][i][j] = (match[k][i][j] && match[size-k][i+k][j+k]) || (match[k][i+size-k][j] && match[size-k][i][j+k]);
return match[len][0][0];
}
```

There are still lots of redundant search in the above methods; can someone further improve it? Thanks in advance!