Interleaving String

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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.

Solution: 1. dp. O(MN) time & space. 'dp[i][j] == true' means that there is at least one way to construct the string s3[0...i+j-1] by interleaving s1[0...j-1] and s2[0...i-1].

代码：

 class Solution {  
 public:  
   //Version 1: dp  
   bool isInterleave(string s1, string s2, string s3) {  
     int M = s1.size(), N = s2.size(), K = s3.size();  
     if (M + N != K) return false;  
     if (s1.empty()) return s2 == s3; // corner case  
     if (s2.empty()) return s1 == s3;  
     vector<vector<bool> > dp(N + 1, vector<bool>(M + 1, false));  
     for (int i = 1; i <= N; ++i)  
       dp[i][0] = s2[i - 1] == s3[i - 1];  
     for (int j = 1; j <= M; ++j)  
       dp[0][j] = s1[j - 1] == s3[j - 1];        
     for (int i = 1; i <= N; ++i) {  
       for (int j = 1; j <= M; ++j) {  
         dp[i][j] = dp[i - 1][j] && s2[i - 1] == s3[i + j - 1] ||  
               dp[i][j - 1] && s1[j - 1] == s3[i + j - 1];          
       }  
     }  
     return dp[N][M];  
   }  
 };