题解 | #交织子序列#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题要求我们判断字符串 t 是否是字符串 s 和 x 的交织子序列，即字符串 t 同时包含了字符串 s 和 x 的子序列，且包含部分不重复，由这两个子序列组成。

思路：我们可以使用动态规划来解决这个问题。我们定义一个二维 dp 数组，其中 dp[i][j] 表示字符串 s 的前 i 个字符和字符串 x 的前 j 个字符能否组成字符串 t 的前 i+j 个字符的交织子序列。

推导状态转移方程：

1. 若 t[i+j] 等于 s[i]，则 dp[i][j] = dp[i-1][j]，表示 s[i] 已经被匹配，继续匹配 s 的下一个字符。
2. 若 t[i+j] 等于 x[j]，则 dp[i][j] = dp[i][j-1]，表示 x[j] 已经被匹配，继续匹配 x 的下一个字符。
3. 否则，dp[i][j] = false，表示当前字符无法匹配。

初始条件：

• dp[0][0] = true，表示空字符串是两个空字符串的交织子序列。
• 当 i = 0 时，dp[0][j] = (x[j-1] == t[j-1]) && dp[0][j-1]，表示 t 的前 j 个字符是否与 x 的前 j 个字符匹配。
• 当 j = 0 时，dp[i][0] = (s[i-1] == t[i-1]) && dp[i-1][0]，表示 t 的前 i 个字符是否与 s 的前 i 个字符匹配。

最后，我们只需要检查 dp[s.length()][x.length()] 的值是否为 true 即可得出答案。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    bool isInterleave(string s, string x, string t) {
        int m = s.length();
        int n = x.length();
        int len = t.length();
        if (m + n != len) {
            return false;
        }

        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;

        // 初始化 dp 数组的第一行和第一列
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = (s[i - 1] == t[i - 1]) && dp[i - 1][0];
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = (x[j - 1] == t[j - 1]) && dp[0][j - 1];
        }

        // 动态规划计算 dp 数组
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if ((s[i - 1] == t[i + j - 1] && dp[i - 1][j]) || (x[j - 1] == t[i + j - 1] && dp[i][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[m][n];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！