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<String> wordBreak(String s, Set<String> wordDict) {
int len = s.length(),maxLen = 0;
result = new String[len];
list = new ArrayList<String>();
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<String> wordDict,int maxLen,int count){
if( pos == s.length() ){
String str = result[0];
for( int i = 1 ; i<count-1;i++){
str =str+ " "+result[i];
}
if( count > 1)
str = str+" "+result[count-1];
list.add(str);
}
int flag = 0;
for( int i = pos;pos - i<maxLen && i<s.length();i++){
if( wordDict.contains( s.substring(pos,i+1) )){
result[count] = s.substring(pos,i+1);
helper(s,i+1,wordDict,maxLen,count+1);
flag = 1;
}
}
}
}
2、加入提前判断是否存在答案（即上一题的结论）就可以了。
public class Solution {
String[] result;
List list;
public List<String> wordBreak(String s, Set<String> wordDict) {
int len = s.length(),maxLen = 0;
result = new String[len];
list = new ArrayList<String>();
for( String str : wordDict ){
maxLen = Math.max(maxLen,str.length());
}
boolean[] dp = new boolean[len];
for( int i = 0 ;i<len;i++){
for( int j = i;j>=0 && i-j<maxLen;j-- ){
if( ( j == 0 || dp[j-1] == true ) && wordDict.contains(s.substring(j,i+1)) ){
dp[i] = true;
break;
}
}
}
if( dp[len-1] == false)
return list;
helper(s,0,wordDict,maxLen,0);
return list;
}
public void helper(String s,int pos,Set<String> wordDict,int maxLen,int count){
if( pos == s.length() ){
String str = result[0];
for( int i = 1 ; i<count-1;i++){
str =str+ " "+result[i];
}
if( count > 1)
str = str+" "+result[count-1];
list.add(str);
}
int flag = 0;
for( int i = pos;pos - i<maxLen && i<s.length();i++){
if( wordDict.contains( s.substring(pos,i+1) )){
result[count] = s.substring(pos,i+1);
helper(s,i+1,wordDict,maxLen,count+1);
flag = 1;
}
}
}
}