力扣 140 单词拆分 II

题意：给定一个字符串和一个字典，返回可以用字典拼接的所有字符串

思路：用set记录字典的单词，用list array记录前i个字符串能够有多少钟组合，然后遍历字符串，在每次遍历中，再从0到i遍历子区间，如果j到i的字符串在字典中，且0到j个字符串有大于0个组合，那么跟新0到i个组合个数

思想：字符串的组合

复杂度：时间O（n^{3)，空间O(n}2)

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        if(s.length() > 100){
            return new ArrayList();
        }
        Set<String> set = new HashSet(wordDict);
        List<String>[] list = new ArrayList[s.length()+1];
        List<String> temp = new ArrayList();
        temp.add("");
        list[0] = temp;
        for(int i=1;i<=s.length();i++) {
            temp = new ArrayList();
            for(int j=0;j<i;j++) {
                String cur = s.substring(j, i);
                if(set.contains(cur) && list[j].size()>0) {
                    for(String str: list[j]) {
                        String t = str + " " + cur;
                        temp.add(t.trim());
                    }
                }
            }
            list[i]=temp;
        }
        return list[s.length()];
    }
}