今天和大家聊的问题叫做 单词拆分 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<String, List<String>> hashMap = new HashMap<>(); public List<String> wordBreak(String s, List<String> wordDict) { if(hashMap.containsKey(s)) { return hashMap.get(s); } List<String> list = new ArrayList<>(); if(0 == s.length()){ list.add(""); return list; } for(String str : wordDict){ if(s.startsWith(str)){ List<String> subList = wordBreak(s.substring(str.length()), wordDict); for(String sub : subList){ list.add(str + (Objects.equals("", sub) ? "" : " ") + sub); } } } hashMap.put(s, list); return list; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
