Lintcode: Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Have you met this question in a real interview? 

Yes

Example

For s1 = "aabcc", s2 = "dbbca"

• When s3 = "aadbbcbcac", return true.
• When s3 = "aadbbbaccc", return false.

Challenge

O(n2) time or better

Tags Expand 

Longest Common Subsequence Dynamic Programming

The intuitive solution is recursion, however, time limit;
//thought
http://blog.csdn.net/u011095253/article/details/9248073
//codes-- tricky c++ solution(unable to find other good c++ recursive version)

Consider worst case  s1 = aaa  s2 = aaa s3 = aaaaaa
Time: best case O(n) worst case O( 2^n)
Space:
stack space depth: O(n) width( 1 to 2^n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class Solution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ bool isInterleave(string s1, string s2, string s3) { // write your code here if(s1.size() + s2.size() != s3.size()) return false; return helper(0, 0, 0, s1, s2, s3); } bool helper(int a, int b, int c, string &s1, string &s2, string &s3){ if(c == s3.size()) return true; // a == s1.size() && b==s2.size() at the same time if(a == s1.size()) { if(s2[b] == s3[c]) return helper(a, b+1, c+1, s1, s2, s3); return false; } if(b == s2.size()){ if(s1[a] == s3[c]) return helper(a+1, b, c+1, s1, s2, s3); return false; } //now a, b, c are all inside their size if(s1[a] == s3[c] && s2[b] == s3[c]){ return helper(a+1, b, c+1, s1, s2, s3) || helper(a, b+1, c+1, s1, s2, s3); } if(s1[a] == s3[c]) return helper(a+1, b, c+1, s1, s2, s3); if(s2[b] == s3[c]) return helper(a, b+1, c+1, s1, s2, s3); return false; } };

Correct solution is DP:
http://www.jiuzhang.com/solutions/interleaving-string/
Note how to express the last char of s3 and the corresponding possible last char of s1 or s2:
We can define i, j
Case 1:
when i, j is the index of the char, s3[i +j+1] corresponds to s1[i] or s2[j ]  <=> D[i, j +1]/D[i+1, j]
case 2:
when i, j is the numbers of char, s3[i+j-1] corresponds to s1[i] or s2[j ]  <=> D[i-1, j]/D[i, j-1]

Assume m = s1.size() n = s2.size()
Case 1:
1. dp[i][j] -- The beginning i+1 digits( index i) and j+1 digits  (index j )of s1 and s2 match to s3(i + j +1)   <====> i+1 + j + 1 - 1
 0 <= i < m; 0 <= j < n
2. if(s[i+j+1] == a[i] && dp[i-1][j]   ||   s[i+j+1]==b[j] && dp[i, j-1])  dp[i][j] = true
However, dp[i][j] has to be sized dp[m+1][n+1] for initial status, so we change i, j in dp to i+1 and j+1, now the 2 equation becomes:
 if(s[i+j+1] == a[i] && dp[i][j+1]   ||   s[i+j+1]==b[j] && dp[i+1, j])  dp[i+1][j+1] = true

case 2:
1. dp[i][j] -- the beginning i digits and j digits of s1 and s2 match the i+j digits of string
2: 1<= i <= m   1 <=j <=n
if s[i + j - 1) == a[ i -1] && dp[i - 1, j]    ||      s[i+j-1] == b[j-1] && dp[i, j-1] :         dp[i][j] = true
3: initial status:
dp[0][0] = true;
for i = 1 to m:    if(s3[i - 1] == s1[i -1])   dp[i][0] = dp[i-1][0];
for j = 1 to n:    if(s3[j - 1] == s2[j - 1])   dp[0][j] = dp[0][j -1];

Time: O(m*n)
Space: O(m*n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ bool isInterleave(string s1, string s2, string s3) { // write your code here if(s1.size() + s2.size() != s3.size()) return false; vector<vector<bool> > dp(s1.size() + 1, vector<bool>(s2.size() + 1, false)); dp[0][0] = true; for(int i = 1; i <= s1.size(); i++){ if(s1[i - 1] == s3[i - 1]) dp[i][0] = dp[i - 1][0]; } for(int j = 1; j <= s2.size(); j++){ if(s2[j - 1] == s3[j - 1]) dp[0][j] = dp[0][j - 1]; } for(int i = 1; i <= s1.size(); i++){ for(int j = 1; j <= s2.size(); j++){ if( (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j]) || (s3[i + j - 1] == s2[j - 1] && dp[i][j - 1]) ){ dp[i][j] = true; } } } return dp[s1.size()][s2.size()]; } };