程式小試身手

有鑑於上一篇,有想到需要Hashmap,確實解答也是這麼用...

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

// DFS function returns an array including all substrings derived from s.
List<String> DFS(String s, Set<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;
}