Word Break II

leetcode 140.

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution. Below code is my classical permutation solution:

public static List<String> wordBreak2(String s, Set<String> wordDict) {
    List<String> ans = new ArrayList<>();
    helper2(s, wordDict, "", ans, 0);
    return ans;
}

// this is the tradition, classical permutation. But it won't memorize the part result.
public static void helper2(String s, Set<String> wordDict, String curr, List<String> ans, int pos) {
    if (pos == s.length()) {
        ans.add(curr.substring(1, curr.length()));
        return;
    }
    for (String word : wordDict) {
        if (pos + word.length() <= s.length() && s.substring(pos, pos + word.length()).equals(word)) {
            helper2(s, wordDict, curr + " " + word, ans, pos + word.length());
        }
    }
}

But it didn’t pass the hot-discussed [a, aa, aaa, …, ], “aaa…aba…aaaaa” test case. The reason is because the traditional permutation doesn’t memorize the history. It just simply permutates all possibilities. Up to now, I haven’t been able to figure out how to use the classical permutation solution to memorize the middle result.

A better solution is that helper function returns a list. The returning list will permutate with current word:

This is another classical permutation solution too. The difference is that this solution takes up more space to memorize each String’s answer.

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

// the helper returns a result list. Put this list into hashmap. This can help to memorize the result.
public static List<String> helper(String s, Set<String> wordDict, Map<String, List<String>> mem) {
    if (mem.containsKey(s)) {
        return mem.get(s);
    }
    List<String> ans = new ArrayList<>();
    if (s.length() == 0) {
        ans.add("");
        return ans;
    }
    for (String word : wordDict) {
        if (s.startsWith(word)) {
            List<String> currList = helper(s.substring(word.length()), wordDict, mem);
            for (String subList : currList) {
                ans.add(word + (subList.isEmpty() ? "" : " ") + subList);
            }
        }
    }
    mem.put(s, ans);
    return ans;
}

Check my code on github.