Straightforward C++ DP solution O(n^4)-time O(n^3)-space

• This solution is based on a previous thread: https://leetcode.com/discuss/13258/my-o-n-4-solution-any-question

The basic idea of this algorithm is to maintain a three-dimension array (henceforth called eq[N][N][N+1]), where (eq[first1][first2][len] == true) if and only if (s1[first1 ... first1+len-1] == s2[first2 ... first2+len-1]). In order to simplify the notation, we discard eq[-][-][0].

Time complexity: O (n^4)

Space complexity: O (n^3)

``````class Solution {
public:
bool isScramble(string s1, string s2) {
bool ret = true;
size_t n = s1.length();
if (n > 0) // if s1 is empty, return true
{
// Dynamic Programming:
// eq[first1][first2][len] == true iff s1[first1 ... first1+len) == s2[first2 ... first2+len)
vector<vector<vector<bool> > > eq
(n, vector<vector<bool>>(n, vector<bool>(n + 1, false))); // initialize: all false

// initialize: eq[first1][first2][1] = true iff s1[first1] == s2[first2]
for (int first1 = 0; first1 < n; ++first1)
{
for (int first2 = 0; first2 < n; ++first2)
{
eq[first1][first2][1] = (s1[first1] == s2[first2]);
}
}

// dp: eq[first1][first2][len] = true iff two substrings are both matched.
for (size_t len = 2; len <= n; ++len)
{
for (size_t first1 = 0; first1 + len <= n; ++first1)
{
for (size_t first2 = 0; first2 + len <= n; ++first2)
{
for (size_t len1 = 1; len1 < len; ++len1)
{
size_t len2 = len - len1;

// two substrings are not swapped
if (eq[first1][first2][len1] && eq[first1 + len1][first2 + len1][len2])
{
eq[first1][first2][len] = true;
}

// two substrings are swapped
if (eq[first1][first2 + len2][len1] && eq[first1 + len1][first2][len2])
{
eq[first1][first2][len] = true;
}
}
}
}
}
ret = eq[0][0][n];
}
return ret;
}
};``````

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