首页 > 代码库 > Interleaving String

Interleaving String

2024-07-20 23:40:20   216人阅读

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

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

 

方法一：递归解，每个字符串，从后往前看，每删除s3一个字符，都必须从s1或s2中删除一个相同的字符，如果找不到相同的字符，那么说明s3并不是s1和s2的交叉而来的字符串，不过大数据超时，不能过，代码如下：

 1 class Solution { 2 public: 3     bool isInterleave(string s1, string s2, string s3) { 4         int len1 = s1.length(); 5         int len2 = s2.length(); 6         int len3 = s3.length(); 7         if( len1 + len2 != len3 ) return false; //要确保s1和s2有可能凑成s3 8         return isInterleaveRecu(s1, len1, s2, len2, s3, len3); 9     }10     11     bool isInterleaveRecu(string&s1, int len1, string& s2, int len2, string& s3, int len3) {12         if( len1 == 0 && len2 == 0 && len3 == 0 ) return true;  //当s1,s2,s3的长度都为0时，说明s1,s2可以交叉成s313         //s1非空且最后一个字符与s3最后一个字符相同，那么就删除s1,s3最后一个字符14         if( len1 > 0 && s1[len1-1] == s3[len3-1] && isInterleaveRecu(s1, len1-1, s2, len2, s3, len3-1) )15             return true;16         //同上原理17         if( len2 > 0 && s2[len2-1] == s3[len3-1] && isInterleaveRecu(s1, len1, s2, len2-1, s3, len3-1) )18             return true;19         return false;20     }21 };

方法二：由递归方程的解法可以推出dp的解法

设dp[i][j]为s1[0...i-1]，s2[0...j-1]交叉构成s3[0...i+j-1]的情况，true即可以构成，false即不能构成

那么当 dp[i-1][j] = true and s1[i-1] = s3[i+j-1] 或 dp[i][j-1] = true and s2[j-1] = s3[i+j-1]的时候，dp[i][j] = true，否则为false，初始化时dp[0][0] = true;

代码如下：

 1 class Solution { 2 public: 3     bool isInterleave(string s1, string s2, string s3) { 4         const int len1 = s1.length(); 5         const int len2 = s2.length(); 6         if( len1 + len2 != s3.length() ) return false;  //依然要确保首要条件 7         bool dp[len1+1][len2+1]; 8         memset(dp, 0, sizeof(dp)); 9         dp[0][0] = true;    //初始化10         for(int i=1; i<=len1; ++i)11             if( dp[i-1][0] && s1[i-1] == s3[i-1] ) dp[i][0] = true;12         for(int j=1; j<=len2; ++j)13             if( dp[0][j-1] && s2[j-1] == s3[j-1] ) dp[0][j] = true;14         for(int i=1; i<=len1; ++i)  //对应讲解中状态转移公式15             for(int j=1; j<=len2; ++j)16                 if( (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1]) )17                     dp[i][j] = true;18         return dp[len1][len2];19     }20 };

 

Interleaving String


联系
我们