# My O(n^4) solution, any question?

• ``````class Solution {
public:
bool isScramble(string s1, string s2) {
if( s1.size() != s2.size() )
return false;
int n = s1.size();
vector<vector<vector<bool> > > dp(n + 1,
vector<vector<bool> >(n, vector<bool>(n, false)));
for(int l = 1; l <= n; ++l)
{
for(int i = 0; i <= n - l; ++i)
{
for(int j = 0; j <= n - l; ++j)
{
if( l == 1 )
dp[l][i][j] = s1[i] == s2[j];
for(int k = 1; k < l; ++k)
{
if( (dp[k][i][j] && dp[l-k][i+k][j+k])
|| (dp[k][i][j+l-k] && dp[l-k][i+k][j]) )
{
dp[l][i][j] = true;
break;
}
}
}
}
}
return dp[n][0][0];
//if( s1.size() == 1 )
//return s1[0] == s2[0];
//int n = s1.size();
//for(int i = 1; i < n; ++i)
//{
//bool first = isScramble(s1.substr(0, i), s2.substr(0, i))
//&& isScramble(s1.substr(i), s2.substr(i));
//bool second = isScramble(s1.substr(0, i), s2.substr(n - i))
//&& isScramble(s1.substr(n - i), s2.substr(0, i));
//if( first || second )
//return true;
//}
//return false;
}
};
``````

Note:
the first for loop enumerate string length;
the second and third for loop enumerate the string begin position;
the fourth try to determine whether s2[i:i+len] is scramble string of s1[j:j+len]

• I found a solution from this blog http://blog.csdn.net/pickless/article/details/11501443.
His DP solution shares the same idea with yours, but the running time is only 24 ms, compared to your 536 ms. However, I think there is a mistake in his code, which also is the only part different from your code.
Here is his code.

``````bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (s1.length() != s2.length()) {
return false;
}
int length = s1.length();
bool f[length][length][length];
memset(f, false, sizeof(bool) * length * length * length);

for (int k = 1; k <= length; k++) {
for (int i = 0; i <= length - k; i++) {
for (int j = 0; j <= length - k; j++) {
if (k == 1) {
f[i][j][k] = s1[i] == s2[j];
}
else {
for (int l = 1; l < k; l++) {
if ((f[i][j][l] && f[i + l][j + l][k - l]) || (f[i][j + k - l][l] && f[i + l][j][k - l])) {
f[i][j][k] = true;
break;
}
}
}
}
}
}

return f[0][0][length];
}
``````

As you can see, f is of size of length * length * length, how can it returns f[0][0][length]?
This confuses me a lot.

• f should be of size length * length * (length+1) , and the f[][][0] are not used, only for better comprehension.

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