# C++ recursive solution with memoization

• recursive solution is rather straightforward based on geeksforgeeks solution - http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/
I've added memoization table so that we can avoid calculating the same result again.

``````// T[i][j] represents the result for s1 with ith index and s2 with jth index
bool isInterleave(string s1, string s2, string s3, vector<vector<int>>& T, int i, int j) {
if (s1.size() == 0 && s2.size() == 0 && s3.size() == 0) return true;

bool first = false, second = false;
if (T[i][j] == -1) {
if (s1.size() && s1[0] == s3[0]) {
first = isInterleave(s1.substr(1), s2, s3.substr(1), T, i+1, j);
T[i][j] = first;
}
if (first) return true;
if (s2.size() && s2[0] == s3[0]) {
second = isInterleave(s1, s2.substr(1), s3.substr(1), T, i, j+1);
T[i][j] = second;
}
}
return T[i][j] == 1;
}

bool isInterleave(string s1, string s2, string s3) {
if (s1.size()+ s2.size() != s3.size()) return false;
// add 1 so we have minimum 1 for empty string to avoid runtime error
vector<vector<int>> T(s1.size()+1, vector<int>(s2.size()+1, -1));
return isInterleave(s1,s2,s3,T,0,0);
}``````

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