题解 | #交织子序列#

知识点：动态规划

思路：

1. 首先，定义一个名为isInterleave的静态方法，该方法接受三个字符串作为参数，并返回一个布尔值。
2. 获取字符串s、x和t的长度，分别记为n、m和N。
3. 如果字符串s和字符串x的长度之和不等于字符串t的长度，则直接返回false，因为长度不匹配，无法交错组成。
4. 创建一个布尔型二维数组f，其大小为(N + 1) × (n + 1)，用于记录状态。
5. 初始化f[0][0]为true，表示空字符串可以由空字符串交错组成。
6. 使用两个嵌套的for循环，遍历t的每个字符并更新状态数组f。
7. 对于每个位置(i, j)，如果s[j - 1]与t[i - 1]相等，则说明可以将s[j - 1]作为新的字符添加到交错字符串中，因此需要判断前一个状态f[i - 1][j - 1]是否为true。
8. 对于每个位置(i, j)，如果x[i - j - 1]与t[i - 1]相等，则说明可以将x[i - j - 1]作为新的字符添加到交错字符串中，因此需要判断前一个状态f[i - 1][j]是否为true。
9. 更新状态数组f[i][j]为上述两种情况的逻辑或运算结果。
10. 循环结束后，返回f[N][n]作为最终的判断结果。
11. 在main方法中，创建一个示例用法，将三个字符串作为参数传递给isInterleave方法，并打印出结果是否为交错字符串的判断结果。

编程语言：java

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) {
        // write code here
        if (s.length() + x.length() != t.length()) {
            return false;
        }
        boolean[][] dp = new boolean[s.length() + 1][x.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            dp[i][0] = (s.charAt(i - 1) == t.charAt(i - 1)) && dp[i - 1][0];
        }
        for (int j = 1; j <= x.length(); ++j) {
            dp[0][j] = (x.charAt(j - 1) == t.charAt(j - 1)) && dp[0][j - 1];
        }
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 1; j <= x.length(); ++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[s.length()][x.length()];
    }
}