140. Word Break II

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

public class Solution {
   Map<String, List<String>> res = new HashMap<String, List<String>>();

    /**
     * DP, Backtracking
     * Store successful decomposition in a map
     * Get prefix
     * If not in dictionary, just ignore
     * If in dictionary, check current position
     * If reaches the end, add prefix to a solution
     * If within length do the following: 
     * Check whether the rest of the string is already decomposed
     * If not, backtracking the rest of the string
     * If yes, get the result from memory function
     * If there is an result, add each word to current solution with front in
     */
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> words = new ArrayList<String>(); 

        int len = s.length();
        for (int i = 1; i <= len; i++) {
            String pref = s.substring(0, i);
            if (dict.contains(pref)) {
                if (i == len) words.add(pref); // reach the end
                else {
                    String remain = s.substring(i, len); // remaining string
                    List<String> remainDecomp = res.containsKey(remain) ?
                        res.get(remain) : wordBreak(remain, dict); // avoid backtracking if a decomposition is already there
                    if (remainDecomp != null) {
                        for (String w : remainDecomp) words.add(pref + " " + w);
                        res.put(remain, remainDecomp); // add to cache
                    }
                }
            }
        }
        return words;
    }
}