LeetCode刷题实战140:单词拆分 II
共 2575字,需浏览 6分钟
·
2020-12-30 17:00
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.
题意
示例 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"]
输出:
[]
解题
public class Solution {
HashMapList > hashMap = new HashMap<>();
public ListwordBreak(String s, List wordDict) {
if(hashMap.containsKey(s)) {
return hashMap.get(s);
}
Listlist = new ArrayList<>();
if(0 == s.length()){
list.add("");
return list;
}
for(String str : wordDict){
if(s.startsWith(str)){
ListsubList = wordBreak(s.substring(str.length()), wordDict);
for(String sub : subList){
list.add(str + (Objects.equals("", sub) ? "" : " ") + sub);
}
}
}
hashMap.put(s, list);
return list;
}
}