​LeetCode刷题实战140:单词拆分 II

程序IT圈

共 2575字,需浏览 6分钟

 ·

2020-12-30 17:00

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 单词拆分 II,我们先来看题面:
https://leetcode-cn.com/problems/word-break-ii/

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.


Note:


The same word in the dictionary may be reused multiple times in the segmentation.

You may assume the dictionary does not contain duplicate words.

题意


给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。


样例

示例 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"
]
解释: 注意你可以重复使用字典中的单词。

示例 3

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]


解题


利用一个hashMap记录某个字符串所能产生的句子的列表。

如果所要寻找的s已经存在在hashMap中,我们直接从hashMap中取得其值即可。否则,我们就需要进入我们的递归函数计算该字符串s所能产生的句子列表。

注意:当s的长度是0时,我们需要往list中添加空字符串元素。同时,在递归调用得到subList列表后,拼接字符串时需要判断所拼接的字符串sub是否为空字符串,如果是空字符串,我们不需要拼接空格字符。

时间复杂度和时间复杂度均与字符串以及字典的情况相关。

public class Solution {
    HashMapList> hashMap = new HashMap<>();
    public List wordBreak(String s, List wordDict) {
        if(hashMap.containsKey(s)) {
            return hashMap.get(s);
        }
        List list = new ArrayList<>();
        if(0 == s.length()){
            list.add("");
            return list;
        }
        for(String str : wordDict){
            if(s.startsWith(str)){
                List subList = wordBreak(s.substring(str.length()), wordDict);
                for(String sub : subList){
                    list.add(str + (Objects.equals("", sub) ? "" : " ") + sub);
                }
            }
        }
        hashMap.put(s, list);
        return list;
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-120题汇总,希望对你有点帮助!
LeetCode刷题实战121:买卖股票的最佳时机
LeetCode刷题实战122:买卖股票的最佳时机 II
LeetCode刷题实战123:买卖股票的最佳时机 III
LeetCode刷题实战124:二叉树中的最大路径和
LeetCode刷题实战125:验证回文串
LeetCode刷题实战126:单词接龙 II
LeetCode刷题实战127:单词接龙
LeetCode刷题实战128:最长连续序列
LeetCode刷题实战129:求根到叶子节点数字之和
LeetCode刷题实战130:被围绕的区域
LeetCode刷题实战131:分割回文串
LeetCode刷题实战132:分割回文串 II
LeetCode刷题实战133:克隆图
LeetCode刷题实战134:加油站
LeetCode刷题实战135:分发糖果
LeetCode刷题实战136:只出现一次的数字
LeetCode刷题实战137:只出现一次的数字 II
LeetCode刷题实战138:复制带随机指针的链表
LeetCode刷题实战139:单词拆分


浏览 24
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报