public class Solution {
public List wordBreak(String s, Set wordDict) {
HashMap> map = new HashMap>();
return dfs(s, wordDict, map);
}
public List dfs(String s, Set wordDict, HashMap> map){
if(map.containsKey(s)) {
return map.get(s);
}
List res = new ArrayList();
if(s.length() == 0){
res.add("");
return res;
}
for(String word: wordDict){
if(s.startsWith(word)){
List remainList = dfs(s.substring(word.length()), wordDict, map);
for(String remain: remainList){
StringBuffer sb = new StringBuffer();
sb.append(word);
if(remain.length() != 0) sb.append(" ");
sb.append(remain);
res.add(sb.toString());
}
}
}
map.put(s, res);
return res;
}
}