/**

public List<String> wordBreak(String s, Set<String> wordDict) {

return dfs(s, wordDict, new HashMap<String, List<String>>());

}

private List<String> dfs(String s, Set<String> wordDict, Map<String, List<String>> map) {

if (s.length() == 0) {

return Arrays.asList("");

}

List<String> result = map.get(s);

if (result != null) {

return result;

} else {

result = new LinkedList<String>();

map.put(s, result);

}

for (String word : wordDict) {

if (s.startsWith(word)) {

List<String> list = dfs(s.substring(word.length()), wordDict, map);

for (String text : list) {

result.add(word + (text.length() > 0 ? " " + text : ""));

}

}

}

return result;

}

/**

public List<String> wordBreak(String s, List<String> wordDict) {

HashMap<String, List<String>> cache = new HashMap<>();

cache.put("", Arrays.asList(""));

return dfs(s, new HashSet<String>(wordDict), cache);

}

private List<String> dfs(String s, HashSet<String> wordDict, HashMap<String, List<String>> cache) {

if (cache.containsKey(s)) {

return cache.get(s);

}

List<String> result = new LinkedList<>();

for (int i = 0; i < s.length(); i++) {

String t = s.substring(i);

if (wordDict.contains(t)) {

List<String> list = dfs(s.substring(0, i), wordDict, cache);

if (list != null) {

for (String ss : list) {

result.add((ss.length() > 0 ? ss + " " : "") + t);

}

}

}

}

cache.put(s, result);

return result;

}