题解 | #交织子序列# 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
        int n = s.length();
        int m = x.length();
        int 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];
    }

}

编程语言是Java。

该题考察的知识点是动态规划。

代码的文字解释：

• isInterleave方法接受三个字符串参数s、x和t，并返回一个布尔值。
• 首先获取字符串s、x和t的长度分别为n、m和k。
• 如果s和x合并起来的长度不等于t的长度k，则直接返回false。
• 创建一个布尔数组f，长度为m+1，用于记录状态转移的结果。
• 初始化f[0]为true，表示空字符串可以由空字符串组成。
• 使用两层循环遍历字符串s和x的每个位置：根据当前位置计算t中对应位置的索引p。如果s的前缀可以与t中对应位置匹配，则将f[j]更新为s.charAt(i - 1) == t.charAt(p)，即取决于之前位置的结果和当前字符是否匹配。如果x的前缀可以与t中对应位置匹配，则将f[j]更新为之前位置的结果f[j - 1]与当前字符是否匹配x.charAt(j - 1) == t.charAt(p)的逻辑或结果。
• 循环结束后，返回f[m]，即表示整个字符串t是否由字符串s和x交错组成的结果。