题解 | #交织子序列#

考察的知识点：动态规划；

解答方法分析：

1. 定义一个布尔型数组f，长度为字符串x的长度加1。数组f的每个元素f[j]表示字符串x的前j个字符是否能够与字符串s和t的某个排列组合成字符串t。
2. 初始化数组f，将第一个元素f[0]设为true，表示空字符串可以与空字符串匹配。
3. 使用两层循环来遍历字符串s和字符串x的所有可能的排列组合。
4. 在循环中，计算当前匹配位置p，即字符串s和字符串x当前考虑的字符在字符串t中的位置。
5. 对于字符串s，若当前的字符s[i-1]与字符串t中的字符t[p]相等，则将当前位置的f]与之前位置的f[j]进行逻辑与运算。
6. 对于字符串x，若当前的字符x[j-1]与字符串t中的字符t[p]相等，则将当前位置的f[j]与前一个位置的f[j-1]`进行逻辑或运算。
7. 最终，返回数组f中最后一个元素f[m]的值，表示字符串x是否能够与字符串s和t组合成字符串t。

所用编程语言：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.length(), m = x.length(), k = t.length();
        if (n + m != k) {
            return false;
        }
        vector<bool> f(m + 1);
        f[0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] = f[j] && (s[i - 1] == t[p]);
                }
                if (j > 0) {
                    f[j] = f[j] || (f[j - 1] && x[j - 1] == t[p]);
                }
            }
        }
        return f[m];
    }
};