97. Interleaving String

Description:

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

Example:

Example 1:

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

Example 2:

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

Link:

https://leetcode.com/problems/interleaving-string/

解题方法：

DP:
We could use dp[i][j] represent if we are able to form the first i + j th substring of s3 (s3.substring(0, i + j)) by the interleaving of the first ith substring of s1 (s1.substring(0, i)) and the first jth substring of s2 (s2.substring(0, j)).
Then for dp[i][j], the new character is s3[i + j - 1], if it is equal to s1[i - 1], which means, we can use s1[i - 1] to match this new character. Then only if dp[i - 1][j] == true (which means s3.substring(0, i + j - 1) could be formed by s1.substring(0, i - 1) and s2.substring(0, j)), dp[i][j] is true.
So we have:

if (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j])
  dp[i][j] = true;

In another hand, we can also have:

if (s3[i + j - 1] == s2[j - 1] && dp[i][j - 1])
  dp[i][j] = true;

Time Complexity：

s1.size() * s2.size()

完整代码：

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int size1 = s1.size(), size2 = s2.size(), size3 = s3.size();
        if(size1 + size2 != size3)
            return false;
        vector<vector<bool>> dp(size1 + 1, vector<bool>(size2 + 1, false));
        for(int i = 0; i <= size1; i++) {
            for(int j = 0; j <= size2; j++) {
                if(i == 0 && j == 0)
                    dp[i][j] = true;
                if(i > 0)
                    if(s1[i - 1] == s3[i + j - 1] && dp[i - 1][j])
                        dp[i][j] = true;
                if(j > 0)
                    if(s2[j - 1] == s3[i + j - 1] && dp[i][j - 1])
                        dp[i][j] = true;
            }
        }
        return dp[size1][size2];
    }
};