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

 

139题的延伸题，需要的出所有结果。

 

1、递归，仍旧超时。

public class Solution {    String[] result;    List list;    public List
     
       wordBreak(String s, Set
      
        wordDict) {        int len = s.length(),maxLen = 0;        result = new String[len];        list = new ArrayList
       
        ();        for( String str : wordDict ){            maxLen = Math.max(maxLen,str.length());        }        helper(s,0,wordDict,maxLen,0);        return list;        }    public void helper(String s,int pos,Set
        
          wordDict,int maxLen,int count){        if( pos == s.length() ){            String str = result[0];            for( int i = 1 ; i
         
           1)                str = str+" "+result[count-1];            list.add(str);        }        int flag = 0;        for( int i = pos;pos - i
         
        
       
      
     

 2、加入提前判断是否存在答案（即上一题的结论）就可以了。

public class Solution {    String[] result;    List list;    public List
     
       wordBreak(String s, Set
      
        wordDict) {        int len = s.length(),maxLen = 0;        result = new String[len];        list = new ArrayList
       
        ();                for( String str : wordDict ){            maxLen = Math.max(maxLen,str.length());        }        boolean[] dp = new boolean[len];        for( int i = 0 ;i
        
         =0 && i-j
         
           wordDict,int maxLen,int count){        if( pos == s.length() ){            String str = result[0];            for( int i = 1 ; i
          
            1) str = str+" "+result[count-1]; list.add(str); } int flag = 0; for( int i = pos;pos - i