97. Interleaving String

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

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...
Note: a + b is the concatenation of strings a and b.

 

Example 1:


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

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

Input: s1 = "", s2 = "", s3 = ""
Output: true
 

Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.
 

Follow up: Could you solve it using only O(s2.length) additional memory space?

这题没有那么简单，我是没想出来要用dp来做，看了别人的思路后写了份dp的实现。

这题首先我们需要找递推公式。递推的依据是s1中放入n个，s2中放入m个，能否符合题意。

然后我们开始递推下一个元素。假设是当s1中放入了n+1个元素，s2中放入m个，能否符合题意。这种情况下，假设此次操作放入的是s1,那么s1对应位置的字符，肯定需要等于s3串中(n+1+m-1)索引处的值，不然肯定不符合题意;同时，假设相等了，那么dp[i-1][j]也必须符合条件才行，假设之前的就不符合题意了，那么我再加一个元素肯定也不符合题意。

同样的，在n+1,m这个选择上，我们还可以选择本身s1就有n+1个元素，s2选取一个元素放入。

最后，我们最后一个值就可判断放入s1长度的元素和s2长度的元素，是否能满足题意。

class InterleavingString : public Solution {
public:
    void Exec() {
        
    }

    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        vector<vector<bool>> dps(s1.size() + 1, vector<bool>(s2.size() + 1, false));
        dps[0][0] = true;

        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s3[i]) {
                break;
            }
            dps[i + 1][0] = true;
        }
        for (int j = 0; j < s2.size(); j++) {
            if (s2[j] != s3[j]) {
                break;
            }
            dps[0][j + 1] = true;
        }
        for (int i = 1; i <= s1.size(); i++) {
            for (int j = 1; j <= s2.size(); j++) {
                dps[i][j] = (s1[i - 1] == s3[i + j - 1] && dps[i - 1][j]) ||
                (s2[j - 1] == s3[i + j - 1] && dps[i][j - 1]);
            }
        }
        return dps.back().back();
    }
};