☆打卡算法☆LeetCode 140. 单词拆分 II 算法解析

恬静的小魔龙 发表于 2022/06/29 11:25:26 2022/06/29
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个字符串s和字符串列表wordDict作为字典,在字符串s中增加空格来构建一个句子,使得句子中所有的单词都在词典中,以任意...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串s和字符串列表wordDict作为字典,在字符串s中增加空格来构建一个句子,使得句子中所有的单词都在词典中,以任意顺序返回这些句子。”

题目链接:

来源:力扣(LeetCode)

链接: 140. 单词拆分 II - 力扣(LeetCode)

2、题目描述

给定一个字符串 s 和一个字符串字典 wordDict ,在字符串 s 中增加空格来构建一个句子,使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意:词典中的同一个单词可能在分段中被重复使用多次。

示例 1:
输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]
示例 2:
输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。

二、解题

1、思路分析

这道题是139题的进阶,139题要求判断是否可以拆分,这道题要求返回所有可能的拆分结果。

139题使用了动态规划思路来判断是否可以拆分,这道题也可以使用动态规划思路,但是如果使用动态规划从下向上拆分,无法提前判断是否可以拆分,在不能拆分的时候会超时。

那么可以使用记忆化搜索,在搜索过程中将不可以拆分的情况进行剪枝。

那么记忆化搜索具体怎么做的?

首先,使用一个哈希表存储字符串s的每个下标和从该下标开始的部分组成的句子列表。

在回溯的过程中,如果遇到已经访问过的下标,可以直接从哈希表中得到结果,不需要重复计算;

如果某个下标无法匹配,则哈希表中该下标对应的是空列表,因此可以对不可以拆分的情况进行剪枝。

2、代码实现

代码参考:

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
        List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
        List<String> breakList = new LinkedList<String>();
        for (List<String> wordBreak : wordBreaks) {
            breakList.add(String.join(" ", wordBreak));
        }
        return breakList;
    }

    public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
        if (!map.containsKey(index)) {
            List<List<String>> wordBreaks = new LinkedList<List<String>>();
            if (index == length) {
                wordBreaks.add(new LinkedList<String>());
            }
            for (int i = index + 1; i <= length; i++) {
                String word = s.substring(index, i);
                if (wordSet.contains(word)) {
                    List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
                    for (List<String> nextWordBreak : nextWordBreaks) {
                        LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
                        wordBreak.offerFirst(word);
                        wordBreaks.add(wordBreak);
                    }
                }
            }
            map.put(index, wordBreaks);
        }
        return map.get(index);
    }
}

image.png

3、时间复杂度

时间复杂度:

时间复杂度为指数级别,无法进行具体分析。

空间复杂度:

空间复杂度为指数级别,无法进行具体分析。

三、总结

对于字符串s 拆分后组成句子,可以有很多种拆分方法,这些其实不是最终答案,但是在记忆化搜索过程中这些结果都会存下来。

这一部分占用的空间至少有O(n * 2n),其实n是字符串的长度,也就是分割方法有2n,每一种方法需要O(n)的字符串进行存储。

对于时间复杂度来说,写入O(n * 2n)空间至少也需要O(n * 2n)的空间,因此时间复杂度同样也是指数级。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。