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.
思路:
可以使用DP的思想来解决这个问题,但是仍然需要一个变量来记录数据,这里dp[i][j]表示使用s1的i个字符 和使用s2的j个字符 能否组成s的i+j个字符。这里需要注意的是dp[0][j]表示s1使用0个字符,s2使用j个字符组成s的前j个字符中,看能否达到要求。
那么对于dp[i][j]来说,如果s1的第i个字符等于当前s的第i+j个字符,也就是s1[i-1] = s[i+j-1],那么只需要判断s1的前i-1个字符和s2的前j个字符能否组成s的前i+j-1个字符.,地推公式如下:
if(s[i+j+1] == s1[i] )
dp[i+1][j+1] = dp[i][j+1] ==1? 1:0;
if(s[i+j+1] == s2[j])
dp[i+1][j+1] = dp[i+1][j] ==1? 1:0;
#include <iostream> #include <vector> #include <string> using namespace std; int Interleaving_str(string& s,string& s1,string& s2) { vector<vector<int> > dp(s1.size()+1); int i,j; for(i=0;i<dp.size();i++) dp[i].assign(s2.size()+1,0); // dp[i][j] 表示用s1 i个字符 用s2 j个字符 dp[0][0] = 0; if(s[0] == s1[0]) dp[1][0] = 1; if(s[0] == s2[0]) dp[0][1] = 1; for(i=1;i<s1.size();i++) if(s1[i] == s[i]) dp[i+1][0] = dp[i][0]==1?1:0; for(j=1;j<s2.size();j++) if(s2[j] == s[j]) dp[0][j+1] = dp[0][j]==1?1:0; for(i=0;i<s1.size();i++) { for(j=0;j<s2.size();j++) { if(s[i+j+1] == s1[i] ) dp[i+1][j+1] = dp[i][j+1] ==1? 1:0; //使用s1 i个字符 和使用 if(s[i+j+1] == s2[j]) dp[i+1][j+1] = dp[i+1][j] ==1? 1:0; //使用s1 i个字符 和使用 if(i==1 && j==0) cout<< dp[i+1][j+1]<<" "<<dp[i+1][j]<<endl; } } return dp[s1.size()][s2.size()]; } int main() { string s("aadbbcbcac"); string s1("aabcc"); string s2("dbbca"); cout<<Interleaving_str(s,s1,s2); return 0; }
原文:http://blog.csdn.net/yusiguyuan/article/details/44647961