582.Word Break II

1.Description(Hard)

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.

Example

Gieve s =lintcode, dict =["de", "ding", "co", "code", "lint"].

A solution is["lint code", "lint co de"].

2.Code

http://www.cnblogs.com/yuzhangcmu/p/4037299.html

Version 1: DFS

与word break类似，但是一个是DP,一个是DFS。

让我们来回顾一下DP与DFS的区别：

DP是Bottom-up 而DFS是TOP-DOWN.

在本题的DFS中，我们这样定义：

用刀在字符串中切一刀。左边是i个字符，右边是len-i个字符。

i: 1- len

如果： 左边是字典里的词，右边是可以wordbreak的，那么把左边的字符串加到右边算出来的List中，生成新的list返回。

1. Base case:

当输入字符串为空的时候，应该给出一个空解。这个很重要，否则这个递归是不能运行的。

1. 递归的时候，i应该从1开始递归，因为我们要把这个问题分解为2个部分，如果你左边给0，那就是死循环。

记忆：

为了加快DFS的速度，我们应该添加记忆，也就是说，算过的字符串不要再重复计算。举例子：

apple n feng

app len feng

如果存在以上2种划分，那么feng这个字符串会被反复计算，在这里至少计算了2次。我们使用一个Hashmap把对应字符串的解记下来，这样就能避免重复的计算。 否则这一道题目会超时。

 public List<String> wordBreak(String s, Set<String> wordDict) {
        if(s==null || s.length()==0 || wordDict==null){
            return null;
        }
        HashMap<String,List<String>> map=new HashMap<String,List<String>>();
        return dfs(s,wordDict,map);

    }

    public List<String> dfs(String s,Set<String> dict,HashMap<String,List<String>> map){
        if(map.containsKey(s)){
            return map.get(s);
        }

        List<String> result=new ArrayList<String>();
        int len=s.length();
        if(len<=0) result.add("");
        //i表示左边字符串的长度
        for(int i=1;i<=len;i++){
            String left=s.substring(0,i);
            //左子串可以为空或者是在字典内
            if(!dict.contains(left)){
                continue;
            }
            //字符串划分为两边，计算右边的word break
            List<String> listright=dfs(s.substring(i),dict,map);
            //右边不能break的时候，跳过
            if(listright.size()==0){
                continue;
            }
            //把左子串加到右子串中，形成新的解
            for(String str:listright){
                StringBuilder sb=new StringBuilder();
                sb.append(left);
                if(i!=0 && i!=len){
                    //如果左边为空或者右边为空时，不需要加空格
                    sb.append(" ");
                }
                sb.append(str);
                result.add(sb.toString());
            }
        }
        map.put(s, result);
        return result;
    }