# Three solutions: recursion, recursion with memory, and DP. Hope this post can help you. :D

• Recursion is time limit exceeted if there are two many the same letters in s1 and s2. Hence we can keep those ways we have tried to save a lot of time. Many DP problems can be solved using recursion with memory.

recursion solution:

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
return isInterleave(s1, s2, s3, 0, 0);
}
bool isInterleave(string &s1, string &s2, string &s3, int a, int b) {
if (s1.empty() && s2.empty() && s3.empty()) return true;
if (s1.size() == a && s2.size() == b) return true;
if (s1.size() == a) {
if (s2[b] != s3[a+b]) return false;
else return isInterleave(s1, s2, s3, a, b+1);
}
if (s2.size() == b) {
if (s1[a] != s3[a+b]) return false;
else return isInterleave(s1, s2, s3, a+1, b);
}
if (s1[a] == s3[a+b] && isInterleave(s1, s2, s3, a+1, b)) return true;
if (s2[b] == s3[a+b] && isInterleave(s1, s2, s3, a, b+1)) return true;
else return false;
}
};
``````

recursion with memory:

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
if (s1.empty() && s2.empty() && s3.empty()) return true;
vector<bool> v(s2.size()+1, false);
vector<vector<bool>> keep(s1.size()+1, v);
return isInterleave(s1, s2, s3, 0, 0, keep);
}
bool isInterleave(string &s1, string &s2, string &s3, int a, int b, vector<vector<bool>>& keep) {
if (keep[a][b]) return false;
keep[a][b] = true;
if (s1.size() == a && s2.size() == b) return true;
if (s1.size() == a) {
if (s2[b] != s3[a+b]) return false;
else return isInterleave(s1, s2, s3, a, b+1, keep);
}
if (s2.size() == b) {
if (s1[a] != s3[a+b]) return false;
else return isInterleave(s1, s2, s3, a+1, b, keep);
}
if (s1[a] == s3[a+b] && isInterleave(s1, s2, s3, a+1, b, keep)) return true;
if (s2[b] == s3[a+b] && isInterleave(s1, s2, s3, a, b+1, keep)) return true;
else return false;
}
};
``````

DP solution:

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
if (s1.empty()) return s2 == s3;
if (s2.empty()) return s1 == s3;
bool dp[s1.size()+1][s2.size()+1];
dp[0][0] = true;
for (int i = 1; i <= s1.size(); ++i) {
if (dp[i-1][0] && s1[i-1] == s3[i-1]) dp[i][0] = true;
else dp[i][0] = false;
}
for (int j = 1; j <= s2.size(); ++j) {
if (dp[0][j-1] && s2[j-1] == s3[j-1]) dp[0][j] = true;
else dp[0][j] = true;
}
for (int i = 1; i <= s1.size(); ++i) {
for (int j = 1; j <= s2.size(); ++j) {
if ((dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1]))
dp[i][j] = true;
else dp[i][j] = false;
}
}
return dp[s1.size()][s2.size()];
}
};>! Spoiler``````

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