public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet(wordDict);
Map<Integer, List<String>> cache = new HashMap();
return breakWord(s, 0, dict, cache);
public List<String> breakWord(String s, int start, Set<String> dict, Map<Integer, List<String>> cache) {
List<String> res = new ArrayList();
if (start == s.length()) {
for (int i = start + 1; i <= s.length(); i++) {
if (dict.contains(s.substring(start, i))) {
List<String> list = new ArrayList();
if (cache.containsKey(i)) {
list = breakWord(s, i, dict, cache);
for (String str : list) {
res.add(s.substring(start, i) + (str.length() == 0 ? "" : " ") + str);