【leetcode】97. 交错字符串（interleaving-string）（DP）[困难]

链接

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

耗时

解题：1 h 11 min
题解：24 min

题意

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

思路

dp[i][j] 表示 s3 的前 i+j 个字符 是否是由 s1 的前 i 个字符 和 s2 的前 j 个字符 交错组成的。
那么可以分为两种情况，

1. s3 的第 i+j 个字符 是 s1 的第 i 个字符，s3 的前 i+j-1 个字符 是由 s1 的前 i-1 个字符 和 s2 的前 j 个字符 交错组成的。
2. s3 的第 i+j 个字符 是 s2 的第 j 个字符，s3 的前 i+j-1 个字符 是由 s1 的前 i 个字符 和 s2 的前 j-1 个字符 交错组成的。

以上两种情况只要有一种成立，即可说明 dp[i][j] 为 true。

状态转移方程：
d p [ i ] [ j ] =         ( s 1 [ i − 1 ] = = s 3 [ i + j − 1 ]   & &   d p [ i − 1 ] [ j ] )                       ∣ ∣   ( s 2 [ j − 1 ] = = s 3 [ i + j − 1 ]   & &   d p [ i ] [ j − 1 ] ) dp[i][j] = \ \ \ \ \ \ \ (s1[i-1] == s3[i+j-1] \ \&\& \ dp[i-1][j]) \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ || \ (s2[j-1] == s3[i+j-1] \ \&\& \ dp[i][j-1]) dp[i][j]=       (s1[i−1]==s3[i+j−1] && dp[i−1][j])                     ∣∣ (s2[j−1]==s3[i+j−1] && dp[i][j−1])

细节：初始化时直接将所有 dp[i][j] 设为 false。dp[i][0] 需要提前处理，即不使用 s2， s3 的前 i 个字符 是否是由 s1 的前 i 个字符组成的，dp[0][j] 同理。

时间复杂度： O ( n m ) O(nm) O(nm)，n 是 s1 的长度，m 是 s2 的长度。

AC代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size()+s2.size()) return false;
        if(s1.size() == 0 || s2.size() == 0) return s3 == s1 || s3 == s2; 
        
        vector<vector<bool>> dp(s1.size()+1, vector<bool>(s2.size()+1, false));

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

        return dp[s1.size()][s2.size()];
    }
};