My code:
public class Solution {
public List<String> wordBreak(String s, Set<String> wordDict) {
return helper(s, new HashMap<String, List<String>>(), wordDict);
}
private List<String> helper(String s, Map<String, List<String>> map, Set<String> wordDict) {
if (map.containsKey(s)) {
return map.get(s);
}
List<String> list = new LinkedList<String>();
if (s.length() == 0) {
list.add("");
return list;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String> ret = helper(s.substring(word.length()), map, wordDict);
for (String part : ret) {
list.add(word + (part.length() == 0 ? "" : " ") + part);
}
}
}
map.put(s, list);
return list;
}
}
看了答案写出来的。
其实思路很简单。就是dfs + memory cache
reference:
https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs/3
time complexity:
O(len(wordDict) ^ len(s / minWordLenInDict))
然后 BFS的做法不知道怎么做。
Anyway, Good luck, Richardo! -- 09/06/2016
