# My DP solution in C++

• `````` bool isInterleave(string s1, string s2, string s3) {

if(s3.length() != s1.length() + s2.length())
return false;

bool table[s1.length()+1][s2.length()+1];

for(int i=0; i<s1.length()+1; i++)
for(int j=0; j< s2.length()+1; j++){
if(i==0 && j==0)
table[i][j] = true;
else if(i == 0)
table[i][j] = ( table[i][j-1] && s2[j-1] == s3[i+j-1]);
else if(j == 0)
table[i][j] = ( table[i-1][j] && s1[i-1] == s3[i+j-1]);
else
table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1] ) || (table[i][j-1] && s2[j-1] == s3[i+j-1] );
}

return table[s1.length()][s2.length()];
}
``````

Here is some explanation:

DP table represents if s3 is interleaving at (i+j)th position when s1 is at ith position, and s2 is at jth position. 0th position means empty string.

So if both s1 and s2 is currently empty, s3 is empty too, and it is considered interleaving. If only s1 is empty, then if previous s2 position is interleaving and current s2 position char is equal to s3 current position char, it is considered interleaving. similar idea applies to when s2 is empty. when both s1 and s2 is not empty, then if we arrive i, j from i-1, j, then if i-1,j is already interleaving and i and current s3 position equal, it s interleaving. If we arrive i,j from i, j-1, then if i, j-1 is already interleaving and j and current s3 position equal. it is interleaving.

• Here is some explanation:

DP table represents if s3 is interleaving at (i+j)th position when s1 is at ith position, and s2 is at jth position. 0th position means empty string.

So if both s1 and s2 is currently empty, s3 is empty too, and it is considered interleaving. If only s1 is empty, then if previous s2 position is interleaving and current s2 position char is equal to s3 current position char, it is considered interleaving. similar idea applies to when s2 is empty. when both s1 and s2 is not empty, then if we arrive i, j from i-1, j, then if i-1,j is already interleaving and i and current s3 position equal, it s interleaving. If we arrive i,j from i, j-1, then if i, j-1 is already interleaving and j and current s3 position equal. it is interleaving.

• Thanks for updating, @sherryxmhe!
I just updated your post with this comment.

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info.

• Great idea using DP!

• so neat! thanks for sharing

• Thanks, great idea!

• Very nice! For your easy understanding, in sherryxmhe's code, i and j can be treated as length of s1, s2 substrings. Further, the cache could be optimized to 1-D vector as below:

``````bool isInterleave(string s1, string s2, string s3) {
int m = s1.length();
int n = s2.length();
int p = s3.length();

if (m + n != p) return false;

//initialize
vector<bool> dp(n + 1);
for (int j = 0; j <= n; j++)    dp[j] = s2.substr(0, j)==s3.substr(0, j);

for (int i = 1; i <= m; i++)
{
dp[0] = s1.substr(0, i)==s3.substr(0, i);
for (int j = 1; j <= n; j++)
dp[j] = (dp[j] && s3[i+j-1]==s1[i-1]) || (dp[j-1] && s3[i+j-1]==s2[j-1]);
}

return dp[n];

}``````

• This post is deleted!

• Hi, sherryxmhe. Your code is really concise and elegant. Thanks for your sharing.

I try to rewrite your code, also in C++, but find that it can only achieve 8ms, not the fastest. I guess handling 2d `vector` may be more time-consuming and thus optimize it to be of `O(min(m, n))` space, but the running time does not change (still 8ms).

Finally, I find that replacing `vector<bool> dp(m, false);` with `bool* dp = new bool[m + 1]();` reduces the running time to 0ms, which is just what I desire. Well, `vector` is really slow...

The code is finally as follows (well, I do not release the allocated memory of `dp`, which is not desirable).

``````class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.length(), n = s2.length(), l = s3.length();
if (m > n) return isInterleave(s2, s1, s3);
if (l != m + n) return false;
bool *dp = new bool[m + 1]();
dp[0] = true;
for (int i = 1; i <= m; i++)
dp[i] = dp[i - 1] && s3[i - 1] == s1[i - 1];
for (int j = 1; j <= n; j++) {
dp[0] = dp[0] && s3[j - 1] == s2[j - 1];
for (int i = 1; i <= m; i++)
dp[i] = (dp[i - 1] && s3[i + j - 1] == s1[i - 1]) || (dp[i] && s3[i + j - 1] == s2[j - 1]);
}
return dp[m];
}
};``````

• Hi, jianchao.li.fighter! Can you explain how can can we use 1-D dp instead of 2-D? And `how` do you come up with the idea? Thank you!

• Hi, rlaoyao. In fact, if a 2d-DP only depends on a single most recent state, then it can be simplified to a 1d-DP. The key to transforming a 2d-DP to a 1d-DP is that you should first write down the 2d-DP code and run it on some examples by drawing the 2d-table. After you become clear of the updating process of the table, you will have an idea of how to reduce the space to 1d. Well, it may be not that obvious at first. But you will gradually get it. Anyway, the key is to practice more :-)

• I have got it! Thanks!

• Hi sherryxmhe, Thanks for your sharing. I rewrite your code in Java and made some modifications(init `dp[i][0]` and `dp[0][i]` in advance), and the code runs faster. :)

``````public static boolean isInterleave(String s1, String s2, String s3) {
int length1 = s1.length(), length2 = s2.length(), length3 = s3.length();
if (length3 != length1 + length2)
return false;
boolean[][] dp = new boolean[length1 + 1][length2 + 1];
for (int i = 0; i <= length1; i++)
dp[i][0] = s1.substring(0, i).equals(s3.substring(0, i)) ? true : false;
for (int i = 1; i <= length2; i++)
dp[0][i] = s2.substring(0, i).equals(s3.substring(0, i)) ? true : false;
for (int i = 1; i <= length1; i++) {
for (int j = 1; j <= length2; j++) {
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return dp[s1.length()][s2.length()];
}``````

• A simple backtracking solution.

``````bool isInterleave(const string &s1, const string &s2, const string &s3, int i, int j, int k, vector<vector<bool>> &visited){
if (k == s3.size()) return true;
if (visited[i][j]) return false;
visited[i][j] = true;
return i < s1.size() && s1[i] == s3[k] && isInterleave(s1, s2, s3, i + 1, j, k + 1, visited) ||
j < s2.size() && s2[j] == s3[k] && isInterleave(s1, s2, s3, i, j + 1, k + 1, visited);
}

bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
vector<vector<bool> > visited(s1.size() + 1, vector<bool>(s2.size() + 1, false));
return isInterleave(s1, s2, s3, 0, 0, 0, visited);
}``````

• Wonderful idea! I just implement your idea with little modification of the code. jianchao.li.fighter already gave optimum solution with single dimension array. So, that will be the best. But, I feel comfortable to understand with 2-D array for this problem. Here is my solution:

``````bool isInterleave(string s1, string s2, string s3) {
int m= s1.size();
int n = s2.size();
int p = s3.size();
if (p!=m+n) return false;
vector<vector<bool>> dp(m+1,vector<bool>(n+1, false));
dp[0][0] = true;

for (int i = 1; i<=m;i++)
dp[i][0] = dp[i-1][0] && s3[i-1] == s1[i-1];
for (int j = 1; j<=n;j++)
dp[0][j] = dp[0][j-1] && s3[j-1] == s2[j-1];

for (int i = 1; i<=m;i++)
for (int j = 1; j<=n;j++)
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
return dp[m][n];
}``````

• Such a brilliant idea!!!
May I ask why is this idea coms into your mind? My first thought is using backtracking to solve this problem, but I found it TLE...

• This is exactly with my thought, share my C++ code.

``````bool isInterleave(string s1, string s2, string s3) {
if (s3.size() != s1.size() + s2.size()) return false;

int m = (int) s1.size();
int n = (int) s2.size();
// dp[i][j] = the first i chars in s1, the first j chars in s2
// can or not can construct to the first (i+j) chars in s3
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
// base case
for (int len = 0; len <= n; ++len) {
dp[0][len] = (s2.substr(0, len) == s3.substr(0, len));
}
for (int len = 0; len <= m; ++len) {
dp[len][0] = (s1.substr(0, len) == s3.substr(0, len));
}

// bottom to up
// the last char in s3[i+j-1] either comes from s1[i-1] or s2[j-1]
// one of them lead to true, then the result is true
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = false;
if (s1[i-1] == s3[i+j-1] && dp[i-1][j] == true) {
dp[i][j] = true;
}
if (s2[j-1] == s3[i+j-1] && dp[i][j-1] == true) {
dp[i][j] = true;
}
}
}
return dp[m][n];
}``````

• bool table[s1.length()+1][s2.length()+1]; Can I ask a c++ question?

You can now indicate a array size with changing variable?

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