# C# DP solution : With thought process

• Pretty Neat DP problem ..
The brute force solution sounds exponential .. given that to exhaust all options for s3 of length N, we need to choose N times whether to pick the character i from s1 or s2.

An interview problem with exponential brute force solution is almost 90+% really a DP one.

Define the state DP[i,j] = True if and only if S1{0-->i} Interleaved with S2{0-->j} will result in S3{0-->i+j}

A closer look may show that DP[i,j] == true if

``````  1. DP[i-1,j] = true AND S3[i+j] = s1[i] (thus we picked the new char from s1)
``````

OR

``````  2. DP[i,j-1] = true AND S3[i+j] = s2[j] (thus we picked the new char from s2)
``````

here's the code:

``````public bool IsInterleave(string s1, string s2, string s3) {
if(s3.Length != s1.Length + s2.Length) return false;

bool[,] dp = new bool[s1.Length+1, s2.Length+1];
dp[0,0] = true;
for(int i=1; i <= s1.Length; i++){
dp[i,0] = dp[i-1,0] && s3[i-1] == s1[i-1];
}

for(int i=1; i <= s2.Length; i++){
dp[0,i] = dp[0,i-1] && s3[i-1] == s2[i-1];
}

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

return dp[s1.Length, s2.Length];
}``````

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