Word Break II 140

Description

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

Hint

DP + backtracking

Method

from problem one we know that we can using i j to spilt string for this question since we need to output all situations so we should use backtracking for a start word it may has many different branch so we can do back from bottom to top

and using map to do memory search

Time & Space

O(len(wordDict) ^ len(s / minWordLenInDict))

for two :

If just using formal backtracking, it will be O(2^n). But this solution, using memo can reduce it to O(n^2),

Let's start form an example. Assume we have a word "leet" and length is four(just forget the dictionary). We want to get final result. Assume we have a function "p()" to solve this solution, that is "res = p(leet)"; In the brut force method(back tracking), we have the following solution: res = Math.min("l" + p("eet") , "le" + p("et") , "lee" + p("t") , "leet"); (for "le" + p("et") the left part is atomic , there is no cut in "le"). we use the cutting position to show every calculate. We can get an recursion tree just like this:0_1473993044618_upload-1c85bf81-e15e-4f20-b3fd-0e3afa3b40a1

but in the memo solution, we don't need to solve subproblems over and over again, we can use the result we have worked out before, so we can pruning the above tree in to0_1473993199026_upload-bcb552c7-5ef8-4fc0-98f1-5ae0233e7944.

(all of the pictures are from "Introduction to Algorithms")

So we can reduce the runtime from exponential-time to polynominal-time.

now we have an dictionary, we even not need to call our recursion function letter by letter so the running time is even less. (I don't calculate the "substring()" into notice because it is build in method)

Code

one :

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
           return dfs(s, wordDict, new HashMap<String, LinkedList<String>>());
    }

    private List<String> dfs(String s, List<String> wordDict, HashMap<String, LinkedList<String>> map){
        if (map.containsKey(s)){
            return map.get(s);
        }
        LinkedList<String> res = new LinkedList<String>();
        if (s.length() == 0){
            res.add("");
            return res;
        }
        for (String word : wordDict){
             if (s.startsWith(word)){
                 List<String> sublist = dfs(s.substring(word.length()), wordDict, map);
                 for (String sub : sublist){
                      res.add(word + (sub.length() == 0? "" : " ") + sub);
                 }
             }
        }
        map.put(s, res);
        return res;
    }

}


``
two:
wordDict may very huge so it is impossible to loop dictionary so we  can do from normal way

public class Solution {
    HashMap<String,List<String>> map = new HashMap<String,List<String>>();
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if(s == null || s.length() == 0) {
            return res;
        }
        if(map.containsKey(s)) {
            return map.get(s);
        }
        if(wordDict.contains(s)) {
            res.add(s);
        }
        for(int i = 1 ; i < s.length() ; i++) {
            String t = s.substring(i);
            if(wordDict.contains(t)) {
                List<String> temp = wordBreak(s.substring(0 , i) , wordDict);
                if(temp.size() != 0) {
                    for(int j = 0 ; j < temp.size() ; j++) {
                        res.add(temp.get(j) + " " + t);
                    }
                }
            }
        }
        map.put(s , res);
        return res;
    }
}

```