字节测开三面算法题(求解)

给出一个字符串 s 和一个词表 wordDict,按照词表对字符串进行切分,排除干扰元素,返回一个子串数组,要求切割后的子串尽可能地覆盖原字符串。

示例 1:
输入:
s = "hecatsanddogllo"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
["cats and dog"]
["cat sand dog"]
任意一个都可。

示例 2:
输入:
s = "hcatsandog"
wordDict = ["cats", "sandog"]
输出:
["sandog"]

示例 3:
输入:
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
["cats", "and"]
["cats", "dog"]
["cat", "sand"]
任意一个都可。
public List<String> wordBreak(String s, Set<String> wordDict) {
    
}

感谢室友提供的答案:   (动态规划还是难啊)
/**
 * dp[i]:表示s中前i个字符最大可以切割的子字符串数组的长度和
 * result[i]存储的 List<String>为: s中前i个字符最大可以切割的子字符串数组
 * 举个例子:s = "catsandog",    wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 因为 ca 没有出现在 wordDict 中,因此 对于s中的前 0/1/2 个字符来说,
 * dp[0]==dp[1]==dp[2]==0     result[0]==result[1]==result[2]==new ArrayList<>()
 * 当i为3时,cat符合条件,因此 dp[3] = 3     result[3] = ["cat"]
 * 当i为4时,cats符合条件,因此 dp[4] = 4     result[4] = ["cats"]
 * 当i为5时,以s中第5个字符'a'为结尾的子字符串没有存在词表里,因此 dp[5] = dp[4]  result[5] = result[4] = ["cats"]
 * 同理   dp[6] = dp[5]     result[6] = result[5] = ["cats"]
 * 当i为7时,s 中 第 4个字符到第7个字符 组成的 子字符串  sand 存在于 词典里,
 * 因此 dp[7] = Math.max(dp[6], dp[4-1] + 7 - 4 + 1)  而 result[7] 也会根据dp[7]的选择,
 * 如果 dp[7] == dp[6] 那么 result[7] = result[6] = ["cats"]
 * 否则的话,result[7] = result[4-1] + s中第4个字符到第7个字符组成的子字符串 = ["cat", "sand"]
 * 后面的依次类推,最后返回 result[i] 中最后一个 List<String> 即为所求。
 */

public static List<String> wordBreak(String s, Set<String> wordDict) {
    int length = s.length();
    int[] dp = new int[length + 1];
    List<String>[] result = new ArrayList[length + 1];
    result[0] = new ArrayList<>();
    dp[0] = 0;
    for (int right = 1; right <= length; ++right) {
        int index = -1;
        int maxLen = 0;
        for (int left = 1; left <= right; ++left) {
            if (wordDict.contains(s.substring(left - 1, right))) {
                int currentLen = right - left + 1 + dp[left - 1];
                if (maxLen < currentLen) {
                    maxLen = currentLen;
                    index = left;
                }
            }
        }
        List<String> currentList;
        if (index == -1 || maxLen < dp[right - 1]) {
            dp[right] = dp[right - 1];
            currentList = new ArrayList<>(result[right - 1]);
        } else {
            dp[right] = maxLen;
            currentList = new ArrayList<>(result[index - 1]);
            currentList.add(s.substring(index - 1, right));
        }
        result[right] = currentList;
    }
    return result[length];
}







#字节跳动内推提前批##面经##校招##字节跳动##测试开发工程师#
全部评论
这个题解没看懂啊
点赞 回复 分享
发布于 2021-08-10 09:30
测开考这么难的题么
点赞 回复 分享
发布于 2021-08-04 21:00
楼主哪个部门啊
点赞 回复 分享
发布于 2021-08-04 15:12
LeetCode140
点赞 回复 分享
发布于 2021-08-03 16:13

相关推荐

07-17 12:14
门头沟学院 Java
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
Hakasee:我的简历和你的基本一样,上周去了上海,boss投了三百家, 三家线下面试 第一家没有做题,全是八股和项目,因为第一次面试不怎么熟练,挂了 第二家,给你几个题目(①css垂直居中文字,字体每两秒闪烁一下以及点击弹窗,②给你一个链接,实现可视化地图,③然后是八股,图片性能优化,以及对图片app有什么想法),45分钟内做完,然后老板面试) 第三家特别偏僻,有点阴森,到了之后让了一个工位给我,有四个题目,①格式化时间 年月日当前时间星期几② 正则表达式提取新闻文字,③在文本域输入文字生成选择题以及选项④生成商品排版还是什么来着 三家都是不超过50人的小公司 两家线上牛客笔试(卡伦特,七牛云,但是笔试不仅要考前端,还要考后端,算法,甚至数学题 我的建议是如果只做了这两个vue项目且不怎么熟练的情况下,先沉淀沉淀,把react学了,上海好的公司基本都是react查看图片
点赞 评论 收藏
分享
07-18 14:55
门头沟学院 Java
点赞 评论 收藏
分享
评论
2
8
分享

创作者周榜

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