public class Solution {
public
ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> result = new
ArrayList<String>();
if(s == null
|| dict.size() == 0)
return
result;
int
len = s.length();
boolean[][] splits = new
boolean[len][len + 1];
for(int
i = len - 1; i >= 0; --i){
splits[i][i] = false;
for(int
j = i + 1; j < len + 1; ++j){
if(dict.contains(s.substring(i, j)))
splits[i][j] = true;
else{
for(int
k = i; k < j; ++k){
splits[i][j] = splits[i][k] && splits[k][j];
if(splits[i][j])
break;
}
}
}
}
if(splits[0][len]){
ArrayList<ArrayList<Integer>> resultInPosition = new
ArrayList<ArrayList<Integer>>();
HashMap<Integer, ArrayList<ArrayList<Integer>> > finished = new
HashMap<Integer,ArrayList<ArrayList<Integer>> >();
for(int
i = len - 1; i >= 0; --i){
ArrayList<ArrayList<Integer>> startAti = new
ArrayList<ArrayList<Integer>>();
if(splits[i][len]){
if(dict.contains(s.substring(i, len))){
ArrayList<Integer> aList = new
ArrayList<Integer>();
aList.add(len);
startAti.add(aList);
}
for(int
j = i + 1; j < len; ++j){
if(dict.contains(s.substring(i,j)) && splits[j][len]){
ArrayList<ArrayList<Integer> > fin = finished.get(j);
for(ArrayList<Integer> ls : fin){
ArrayList<Integer> temp = new
ArrayList<Integer>();
temp.add(j);
temp.addAll(ls);
startAti.add(temp);
}
}
}
}
finished.put(i, startAti);
}
resultInPosition = finished.get(0);
for(ArrayList<Integer> ls : resultInPosition){
int
lssize = ls.size();
int
first = ls.get(0);
String resultString = s.substring(0, first);
for(int
i = 1; i < lssize; ++i){
resultString += (" "+ s.substring(first, ls.get(i)));
first = ls.get(i);
}
result.add(resultString);
}
}
return
result;
}
}
