// 官方
// https://leetcode-cn.com/problems/word-break-ii/solution/dan-ci-chai-fen-ii-by-leetcode-solution/
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
List<String> breakList = new LinkedList<String>();
for (List<String> wordBreak : wordBreaks) {
breakList.add(String.join(" ", wordBreak));
}
return breakList;
}
public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
if (!map.containsKey(index)) {
List<List<String>> wordBreaks = new LinkedList<List<String>>();
if (index == length) {
wordBreaks.add(new LinkedList<String>());
}
for (int i = index + 1; i <= length; i++) {
String word = s.substring(index, i);
if (wordSet.contains(word)) {
List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
for (List<String> nextWordBreak : nextWordBreaks) {
LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
wordBreak.offerFirst(word);
wordBreaks.add(wordBreak);
}
}
}
map.put(index, wordBreaks);
}
return map.get(index);
}
}
// 超时
class Solution {
Map<Integer, List<String>> map = new HashMap<>();
Set<String> set = new HashSet<>();
int maxL = 0;
public List<String> wordBreak(String s, List<String> wordDict) {
for(String word: wordDict){
set.add(word);
maxL = Math.max(maxL, word.length());
}
for(int i = s.length()-1; i>=0; i--){
core(s, i);
}
return map.getOrDefault(0, new ArrayList<>());
}
private void core(String s, int cur){
String tar = s.substring(cur, s.length());
List<String> saveList = new ArrayList<>();
if(set.contains(tar)){
saveList.add(tar);
}
for(int i = cur+1; i<s.length() && i<=cur+maxL; i++){
if(!map.containsKey(i))
continue;
tar = s.substring(cur, i);
if(!set.contains(tar))
continue;
List<String> ListI = map.get(i);
for(String endStr : ListI){
saveList.add(tar + " " + endStr);
}
}
if(cur+maxL<s.length())
map.remove(cur+maxL);
if(saveList.size()!=0)
map.put(cur, saveList);
}
}
原文:https://www.cnblogs.com/BWSHOOTER/p/13912228.html