interleaving string

interleaving string

Dynamic progaming

This problem is a dynamic programing problem.Assuming that dp[i][j] stands for whether s1.substr(0,i)ands2.substr(0,j) can form s3.substr(0,i+j). And dp[i][j] can be transformed from dp[i-1][j] or dp[i][j-1] The transfer equation is 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] ).

 1 class Solution {
 2 public:
 3     bool isInterleave(string s1, string s2, string s3) {
 4         int l1 = s1.length();
 5         int l2 = s2.length();
 6         if ( l1+l2 != s3.length() ) {
 7             return false;
 8         }
 9         if ( 0 == l1 ){
10             return s2 == s3;
11         }
12         if ( 0 == l2 ) {
13             return s1 == s3;
14         }
15         bool dp[l1+1][l2+1];
16         memset(dp,0,sizeof(dp));
17         dp[0][0] = 1;
18         for ( int i = 1; i <= l1; i++ ){
19             dp[i][0] = dp[i-1][0]&&(s1[i-1] == s3[i-1]);
20         }
21         for ( int j = 1; j <= l2; j++ ) {
22             dp[0][j] = dp[0][j-1]&&(s2[j-1] == s3[j-1]);
23         }
24         for ( int i = 1; i <= l1; i++ ) {
25             for ( int j = 1; j <= l2; j++ ) {
26                 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] ) ) );
27             }
28         }
29         return dp[l1][l2];
30     }
31 };

Loading Disqus comments...
Table of Contents