题解 | #交错编号# 动态规划

知识点

动态规划

思路

因为要求刚好匹配 所以

不满足则不可以, 所以 

定义f[i][j] 表示t的前i个字符 是否满足能 s前i个字符和x的前i-j个字符匹配

由于  所以状态数最多20000个

每次状态转移, 讨论当前t中的字符和哪一个字符串的字符相匹配, 单次转移的时间复杂度为

总的时间复杂度 

AC Code (c++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s1 string字符串 
     * @param s2 string字符串 
     * @param s3 string字符串 
     * @return bool布尔型
     */
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size(), m = s2.size(), N = s3.size();
        if (m + n != N) return false;
        vector<vector<bool>> f(N + 1, vector<bool>(n + 1, false));
        // f[i][j] t前i个字符 是否满足 s前i个字符和 和x的前i-j个字符
        f[0][0] = true;
        for (int i = 1; i <= N; i ++) {
            for (int j = 0; j <= i; j ++) {
                if (j and s3[i - 1] == s1[j - 1]) f[i][j] = (f[i][j] or f[i - 1][j - 1]);
                if (i - j and s3[i - 1] == s2[i - j - 1]) f[i][j] = (f[i][j] or f[i - 1][j]);
            }
        }
        return f[N][n];
    }
};