学步园

Interleaving
String:

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.

试了下跟归并一样的贪心思路，果然是不行的，比如 s1= "aa", s2="ab", s3="aaba" 贪心就不行，因为在s1[i] ,s2[j] 都和s3中字母相等的时候，你不知道应该用哪一个。

那就老老实实DP吧，下面空间还可以优化成O(n)的。

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        
    	int len1=s1.length(),len2=s2.length(),len3=s3.length();
		if ( len1+len2!=len3 )
			return false;
		vector<vector<int> > dp(len1+1,vector<int>(len2+1,0));
		dp[0][0]=1;
		for(int i=1;i<=len1;i++)
			dp[i][0]=dp[i-1][0]&&s1[i-1]==s3[i-1];
		for(int i=1;i<=len2;i++)
			dp[0][i]=dp[0][i-1]&&s2[i-1]==s3[i-1];
		
		for(int i=1;i<=len1;i++)
		{
			for(int j=1;j<=len2;j++)
			{
				int p1=i-1,p2=j-1,p3=i+j-1;
				dp[i][j]= (dp[i-1][j]&&s1[p1]==s3[p3])||(dp[i][j-1]&&s2[p2]==s3[p3]);
			}
		}
		return dp[len1][len2]==1;
    }
};