国产在线,韩国乱伦网站,操逼内射网站,我要看一级黄片,字幕一区二区三区四区五区在线看 ,日皮视频在线入口,欧美一级A片免费看,水蜜桃无码观看

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從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，在字符串中增加空格來構(gòu)建一個句子，使得句子中所有的單詞都在詞典中。返回所有這些可能的句子。

說明：

拆分時可以重復(fù)使用字典中的單詞。

你可以假設(shè)字典中沒有重復(fù)的單詞。

樣例

示例 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"
]
解釋: 注意你可以重復(fù)使用字典中的單詞。

示例?3：

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

解題

利用一個hashMap記錄某個字符串所能產(chǎn)生的句子的列表。

如果所要尋找的s已經(jīng)存在在hashMap中，我們直接從hashMap中取得其值即可。否則，我們就需要進(jìn)入我們的遞歸函數(shù)計算該字符串s所能產(chǎn)生的句子列表。

注意：當(dāng)s的長度是0時，我們需要往list中添加空字符串元素。同時，在遞歸調(diào)用得到subList列表后，拼接字符串時需要判斷所拼接的字符串sub是否為空字符串，如果是空字符串，我們不需要拼接空格字符。

時間復(fù)雜度和時間復(fù)雜度均與字符串以及字典的情況相關(guān)。

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;
????}
}