题解 | #交织子序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param x string字符串
     * @param t string字符串
     * @return bool布尔型
     */
    public boolean 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;
        }

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

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

        for (int j = 1; j <= n; ++j) {
            dp[0][j] = (x.charAt(j - 1) == t.charAt(j - 1)) && dp[0][j - 1];
        }

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

        return dp[m][n];
    }
  // 方法二：
    // int n = s.length(), m = x.length(), k = t.length();
    //     if (n + m != k) {
    //         return false;
    //     }
 
    //     boolean[] f = new boolean[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] &= (s.charAt(i - 1) == t.charAt(p));
    //             }
    //             if (j > 0) {
    //                 f[j] |= (f[j - 1] && x.charAt(j - 1) == t.charAt(p));
    //             }
    //         }
    //     }
 
    //     return f[m];
    // }
}

知识点:

动态规划

解题分析：

1. 定义一个大小为m+1的布尔型数组f，表示字符串x的前j个字符和字符串s的前i个字符是否能够交错组成字符串t的前i+j个字符。
2. 初始化数组f的第一个元素为true，表示空字符串可以由空字符串组成。
3. 使用两层循环遍历数组f，其中i表示字符串s的前i个字符，j表示字符串x的前j个字符：计算当前位置在字符串t中的索引p = i + j - 1。如果i大于0，则判断s的第i个字符是否与t的第p个字符相等，并更新f[j]的值为f[j]与(s.charAt(i-1) == t.charAt(p))的逻辑与结果。如果j大于0，则判断x的第j个字符是否与t的第p个字符相等，并更新f[j]的值为f[j]或(f[j-1] && x.charAt(j-1) == t.charAt(p))的逻辑或结果。
4. 返回f[m]的值，即字符串x的全部字符和字符串s的全部字符是否能够交错组成字符串t的全部字符。

编程语言：

java