算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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 {HashMap> hashMap &#61; new HashMap<>();public List wordBreak(String s, List wordDict) {if(hashMap.containsKey(s)) {return hashMap.get(s);}List list &#61; new ArrayList<>();if(0 &#61;&#61; s.length()){list.add("");return list;}for(String str : wordDict){if(s.startsWith(str)){List subList &#61; wordBreak(s.substring(str.length()), wordDict);for(String sub : subList){list.add(str &#43; (Objects.equals("", sub) ? "" : " ") &#43; sub);}}}hashMap.put(s, list);return list;}
}
好了&#xff0c;今天的文章就到这里&#xff0c;如果觉得有所收获&#xff0c;请顺手点个在看或者转发吧&#xff0c;你们的支持是我最大的动力。
上期推文&#xff1a;
LeetCode1-120题汇总&#xff0c;希望对你有点帮助&#xff01;
LeetCode刷题实战121&#xff1a;买卖股票的最佳时机
LeetCode刷题实战122&#xff1a;买卖股票的最佳时机 II
LeetCode刷题实战123&#xff1a;买卖股票的最佳时机 III
LeetCode刷题实战124&#xff1a;二叉树中的最大路径和
LeetCode刷题实战125&#xff1a;验证回文串
LeetCode刷题实战126&#xff1a;单词接龙 II
LeetCode刷题实战127&#xff1a;单词接龙
LeetCode刷题实战128&#xff1a;最长连续序列
LeetCode刷题实战129&#xff1a;求根到叶子节点数字之和
LeetCode刷题实战130&#xff1a;被围绕的区域
LeetCode刷题实战131&#xff1a;分割回文串
LeetCode刷题实战132&#xff1a;分割回文串 II
LeetCode刷题实战133&#xff1a;克隆图
LeetCode刷题实战134&#xff1a;加油站
LeetCode刷题实战135&#xff1a;分发糖果
LeetCode刷题实战136&#xff1a;只出现一次的数字
LeetCode刷题实战137&#xff1a;只出现一次的数字 II
LeetCode刷题实战138&#xff1a;复制带随机指针的链表
LeetCode刷题实战139&#xff1a;单词拆分