题解 | #交织子序列#

交织子序列

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

测试用例不全,下面的错误代码也能A

import java.util.*;


public class Solution {

    public boolean isInterleave (String s, String x, String t) {
        int sIndex = s.length() - 1;
        int xIndex = x.length() - 1;
        int tIndex = t.length() - 1;

        while (tIndex >= 0 && sIndex >= 0 && xIndex >= 0) {
            if (t.charAt(tIndex) == s.charAt(sIndex)) {
                tIndex--;
                sIndex--;
            } else if (t.charAt(tIndex) == x.charAt(xIndex)) {
                tIndex--;
                xIndex--;
            } else {
                return false;
            }
        }

        return true;
    }
}

这题用动态规划才是正解

import java.util.*;


public class Solution {

    public boolean isInterleave (String s, String x, String t) {
        if (s.length() + x.length() != t.length()) return false;

        // dp[i][j] 表示字符串 s 的前 i 个字符和字符串 x 的前 j 个字符能否组成字符串 t 的前 i+j 个字符的交织子序列。
        boolean[][] dp = new boolean[s.length() + 1][x.length() + 1];

        // 初始化dp数组
        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 i = 1; i <= x.length(); i++) {
            dp[0][i] = (x.charAt(i - 1) == t.charAt(i - 1)) && dp[0][i - 1];
        }

        // dp start
        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()];
    }
}

算法题刷刷刷 文章被收录于专栏

数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
吴offer选手:HR:我KPI到手了就行,合不合适关我什么事
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务