LeetCode解题报告（390) -- 97. Interleaving String

Problem

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:

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

Example 2:

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

Example 3:

1 2	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?

Analysis

题目给出两个字符串s1和s2，同时还给出了一个s3，问能否通过交织s1和s2得到s3？实际上就是在s3中找到哪些字符是从s1来的，哪些是从s2来的。这类问题直接就是往dp方向考虑。

定义dp[i][j]为由s1前i个字符和s2前j个字符能否匹配s3的前i + j个字符。首先考虑边界情况，即只有s1或只有s2的case，转移方程为：

dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1]；
dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1]

然后再来看中间状态的转移：

dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])；

可以看出s3[i + j - 1]是由两部分共同决定的，这个位置的字符既可以是由s1提供的s1[i - 1]，也可以是由s2提供的s2[j - 1]。

Solution

这里还有一个技巧是可以在一开始先通过长度过滤掉一部分不符合要求的case。

Code

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));
        dp[0][0] = true;
        for (int i = 1; i <= size1; i++) {
            dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
        }
        
        for (int j = 1; j <= size2; j++) {
            dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);
        }
        
        for (int i = 1; i <= size1; i++) {
            for (int j = 1; j <= size2; j++) {
                dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) || (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]));
            }
        }
        return dp[size1][size2];
    }
};

Summary

这道题是难度中等的字符串dp，字符串的dp了总体思路是比较清晰的，用一个二维dp，然后分别从两个字符串中取字符做对比。这道题目的分享到这里，感谢你的支持！