题解 | #交织子序列# DP

知识点

动态规划

思路

因为要求刚好匹配所以 $len(s) + len(x)=len(t)$

不满足则不可以, 所以 $len(t) \leq 200$

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

由于 $len(t) \leq 200$ 所以状态数最多20000个

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

总的时间复杂度 $O(n^2)$

AC Code (c++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param x string字符串 
     * @param t string字符串 
     * @return bool布尔型
     */
    bool isInterleave(string s, string x, string t) {
        int n = s.size(), m = x.size(), N = t.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 t[i - 1] == s[j - 1]) f[i][j] = (f[i][j] or f[i - 1][j - 1]);
                if (i - j and t[i - 1] == x[i - j - 1]) f[i][j] = (f[i][j] or f[i - 1][j]);
            }
        }
        return f[N][n];
    }
};