import java.util.*;
/**
* Source : https://oj.leetcode.com/problems/word-break-ii/
*
* 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"].
*/
public class WordBreak2 {
/**
* 找到所有可能的分割方法，使得分割后的单词在dic中
*
* 使用DFS
*
* @param str
* @param dic
* @return
*/
public String[] wordBreak (String str, Set<String> dic) {
List<String> result = new ArrayList<String>();
List<String> solution = new ArrayList<String>();
recursion(str, dic, solution, result);
return result.toArray(new String[solution.size()]);
}
private void recursion (String str, Set<String> dic, List<String> solution, List<String> result) {
if (str.length() == 0 && solution.size() > 0) {
StringBuffer stringBuffer = new StringBuffer();
for (String word : solution) {
stringBuffer.append(word);
stringBuffer.append(" ");
}
result.add(stringBuffer.substring(0, stringBuffer.length()-1));
}
for (int i = 0; i < str.length(); i++) {
if (dic.contains(str.substring(0, i+1))) {
solution.add(str.substring(0, i+1));
recursion(str.substring(i+1, str.length()), dic, solution, result);
solution.remove(solution.size()-1);
}
}
}
public static void main(String[] args) {
WordBreak2 wordBreak2 = new WordBreak2();
String[] dicStr = new String[]{"cat", "cats", "and", "sand", "dog"};
System.out.println(Arrays.toString(wordBreak2.wordBreak("catsanddog", new HashSet<String>(Arrays.asList(dicStr)))));
}
}