0097 Interleaving String

Problem Description

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

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Solution

The problem can be solved by dynamic programming. The key point is to define the sub-problem and identify the number of sub-problems. Normally, we could take the extreme case or the trivial case to get start and build the logic.

In this case, for example, we start from the case where s1 and s2 are all empty and we use i=0;j=0; to denote it. Then the empty string can be said to be interleaved from these two empty strings. (trivial case or the base case.) Next we progress to the case i=0;j=1;, that is the empty string "" and s2[0] or s2[j-1], and we compare to s3[0] or s3[i+j-1] to check, it's either true meaning the i=0;j=1; case can form the prefix of s3: s3[0], or false meaning i=0;j=1; case can not form the prefix of s3: s3[0]. Then we continue by looping over index j until the end of length of s2. And similarly we will loop over on index i also.

As can be seen above, the sub-problem we could define is to check if substring of s1 (s1[:i]) and substring of s2 (s2[:j]) could form the prefix of s3: s3[:i+j]. Therefore the number of such sub-problems is: s1.size.() * s2.size() and we can use a two dimensional array dp[i][j] to store the result for each sub-problem. The final goal is to check if the whole s1 string and s2 string can form the whole s3 string, that is dp[s1.size()][s2.size()]. For each sub-problem, we only consider one more char, that is to compare the char s3[i+j-1] with the last char in the substring s1[i-1] and s2[j-1]. There're two options in order for dp[i][j] to be true:

  • if s3[i+j-1]==s1[i-1] is true, and we only need to check if dp[i][j-1] is true
  • if s3[i+j-1]==s2[j-1] is true, and we only need to check if dp[i-1][j] is true

a C++ code

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.size(), len2 = s2.size();
        if(s3.size() != len1+len2) return false; // to check the length of s3 must match
        vector<vector<int> > dp = vector(len1+1, vector<int>(len2+1, 0));
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                if(i==0 && j==0) dp[i][j] = 1;
                else if(i==0) dp[i][j] = (s3[i+j-1]==s2[j-1]) && dp[i][j-1];
                else if(j==0) dp[i][j] = (s3[i+j-1]==s1[i-1]) && dp[i-1][j];
                else{
                    dp[i][j] = ( s3[i+j-1]==s2[j-1] && dp[i][j-1] ) || ( s3[i+j-1]==s1[i-1] && dp[i-1][j] );
                }
            }
        }
        return dp[len1][len2];
    }  
};

Observing the code, we could see under the inner for loop, we only need the vector from the last time. Thus we could optimize the memory usage by defining an one dimension array dp[j], as can be seen below:

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.size(), len2 = s2.size();
        if(s3.size() != len1+len2) return false;
        vector<int> dp = vector<int>(len2+1, 0); // one dimention dp array
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                if(i==0 && j==0) dp[j] = 1;
                else if(i==0) dp[j] = (s3[i+j-1]==s2[j-1]) && dp[j-1];
                else if(j==0) dp[j] = (s3[i+j-1]==s1[i-1]) && dp[j];
                else{
                    dp[j] = ( s3[i+j-1]==s2[j-1] && dp[j-1] ) || ( s3[i+j-1]==s1[i-1] && dp[j] );
                }
            }
        }
        return dp[len2];
    }  
};
文章目录