DP

状态表示： f[i][j]表示由s1[1 - i]和s2[1 - j]交错形成s3[1 - i + j] 的所有方案是否合法

状态方程为：

• 当s1的末尾和s3的末尾匹配上，即当s1[i] == s3[i + j]时，f[i][j] = f[i - 1][j]
• 当s2的末尾和s3的末尾匹配上，即当s2[i] == s3[i + j]时，f[i][j] = f[i][j - 1]

$ 时间复杂度O(NM)，空间复杂度O(NM) $

参考文献

lc究极班

AC代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size();
        if (n + m != s3.size()) return false;//特判长度不相等
        vector<vector<bool>> f(n + 1,vector<bool>(m + 1, false));
        s1 = ' ' + s1;
        s2 = ' ' + s2;
        s3 = ' ' + s3;
        //DP
        for (int i = 0 ; i <= n ; i ++){
            for (int j = 0 ; j <= m ; j ++){
                if (!i && !j) f[i][j] = true;//初始化,空串可以匹配
                else {
                    if (i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
                    if (j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
                }
            }
        }
        return f[n][m];

    }
};