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(), 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];
    }
}

编程语言是Java。

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

代码的文字解释如下：

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的全部字符。