题解 | #交织子序列#

交织子序列

https://www.nowcoder.com/practice/3885d44d77f34f1c89dc05ac40207f5d

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

全部评论

相关推荐

ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务