Combination of Construction of String from Dictionary(Word Break)

题目地址：
https://leetcode.com/problems/word-break-ii/description/

题目：
面试版：

假如input字符串可以任意拆分成n个子字符串，输出所有的可能。
dic{aa, ab, star, b, a}
input: aab
output:{(a, a, b), (aa, b), (a, ab)}


Leetcode版：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

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

解题思路：
这道题就是常规的dfs。

代码:

public class CombinationofConstructionofStringfromDictionary {

    public List<List<String>> findCombinations(Set<String> dict, String s){
        List<List<String>> rst = new ArrayList<>();
        if(s == null || s.length() == 0){
            return rst;
        }
        List<String> list = new ArrayList<>();
        helper(dict, s, rst, list, 0);
        return rst;
    }

    private void helper(Set<String> dict, String s, List<List<String>> rst, List<String> list, int pos){
        if(pos == s.length()){
            rst.add(new ArrayList<>(list));
            return;
        }
        for(int i = pos; i <= s.length() - 1; i++){
            String temp = s.substring(pos, i + 1);
            if(dict.contains(temp)){
                list.add(temp);
                helper(dict, s, rst, list, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args){
        CombinationofConstructionofStringfromDictionary combinationofConstructionofStringfromDictionary = new CombinationofConstructionofStringfromDictionary();
        Set<String> dict = new HashSet<>();
        dict.add("aa");
        dict.add("ab");
        dict.add("star");
        dict.add("b");
        dict.add("a");
        String s = "aab";
        List<List<String>> rst = combinationofConstructionofStringfromDictionary.findCombinations(dict, s);
        System.out.println(rst);
    }

}