LeetCode Word Break II

// Given a non-empty string s without space and a dictionary wordDict containing a list of non-empty words, convert the input string into string with spaces. You may assume the dictionary does not contain duplicate words.

// For example, given
// s = "leetcode",
// dict = ["leet", "code"].

// Return "leet code" because "leetcode" can be segmented as "leet code".

public class WordBreakII {
 
public List<String> wordBreak(String s, List<String> wordDict) {
          return DFS(s, wordDict, new HashMap<String, LinkedList<String>>());
}     

// DFS function returns an array including all substrings derived from s.
public List<String> DFS(String s, List<String> wordDict, HashMap<String, LinkedList<String>>map) {
if (map.containsKey(s))
return map.get(s);

LinkedList<String>res = new LinkedList<String>();   
if (s.length() == 0) {
res.add("");
return res;
}             
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String>sublist = DFS(s.substring(word.length()), wordDict, map);
for (String sub : sublist)
res.add(word + (sub.isEmpty() ? "" : " ") + sub);             
}
}     
map.put(s, res);
return res;
}
}