140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

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"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution:

We use DFS + memorization to solve this problem.

For a giving string s, we can break it into two half: s.substring(0, i) and s.substring(i).

If s.substring(i) is in the dictionary, we can:

1. Break s.substring(0, i). Let's say the result is tmp (all possible combinations).

2. For each combination comb in tmp, we create comb + " " + s.substring(i), to form a valid combination of s, and add it to the result list.

After dealing with the current string s, don't forget to add its results to the HashMap such that we do not need to calculate it again.



Code:

public class Solution {
    
    public HashMap<String, List<String>> map = new HashMap<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        if (map.containsKey(s)) {
            return map.get(s);
        }
        if (wordDict.contains(s)) {
            res.add(s);    
        }
        for (int i = 1; i < s.length(); i++) {
            String suffix = s.substring(i);
            if (wordDict.contains(suffix)) {
                List<String> list = wordBreak(s.substring(0, i), wordDict);
                for (String str : list) {
                    res.add(str + " " + suffix);
                }
            }
        }
        map.put(s, res);
        return res;
    }
}