解法

回溯，记忆化，动态规划，动态规划的话，仍然会时间超时，对于一长串aaaa的情况

代码

回溯

   //我的解法 
    public static List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res=new ArrayList<>();
        f(s,wordDict,0,new String(),res);
        return res;
    }
    public static void f(String s,List<String> wordDict,int index,String temp,List<String> res)
    {
        //base case
        if(index==s.length())
        {
            res.add(temp);
            return ;
        }
        for(int i=index;i<s.length();i++)
        {
            if(wordDict.contains(s.substring(index,i+1)))
            {
                temp=temp.equals("")?s.substring(index,i+1):temp+" "+s.substring(index,i+1);
                f(s,wordDict,i+1,temp,res);
                temp=temp.lastIndexOf(" ")==-1?"":temp.substring(0,temp.lastIndexOf(" "));
            }
        }
    }


//官方的解法
public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> f = f(s, 0, wordDict);
        return f;
    }
    public List<String> f(String s,int index,List<String> wordDict)
    {
        List<String> res=new ArrayList<>();
        if(index==s.length())
        {
            res.add("");
        }
        for(int i=index+1;i<=s.length();i++)
        {
            if(wordDict.contains(s.substring(index,i))) {
                String temp = s.substring(index, i);
                List<String> list = f(s, i, wordDict);
                for (String str : list) {
                    if(str.equals(""))
                    res.add(temp);
                    else
                    res.add(temp+" "+str);
                }
            }
        }
        return res;
    }

记忆化

在官方的解法中，多加一个map就可以了

public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> f = f(s, 0, wordDict);
        return f;
    }
    public HashMap<Integer,List<String>> map=new HashMap<>();
    public List<String> f(String s,int index,List<String> wordDict)
    {
        if(map.containsKey(index))
        {
            return map.get(index);
        }
        List<String> res=new ArrayList<>();
        if(index==s.length())
        {
            res.add("");
        }
        for(int i=index+1;i<=s.length();i++)
        {
            if(wordDict.contains(s.substring(index,i))) {
                String temp = s.substring(index, i);
                List<String> list = f(s, i, wordDict);
                for (String str : list) {
                    if(str.equals(""))
                    res.add(temp);
                    else
                    res.add(temp+" "+str);
                }
            }
        }
        map.put(index,res);
        return res;
    }

动态规划

   public List<String> wordBreak(String s, List<String> wordDict) {
        List<String>[] dp=new List[s.length()+1];
        List<String> init=new ArrayList<>();
        init.add("");
        dp[0]=init;
        for(int i=1;i<=s.length();i++)
        {
            dp[i]=new ArrayList<>();
            for(int j=0;j<i;j++)
            {
                if(dp[j].size()>0&&wordDict.contains(s.substring(j,i)))
                {
                    for(String temp:dp[j])
                    {
                        if(temp.equals(""))
                        {
                            dp[i].add(temp+s.substring(j,i));
                        }else
                        {
                            dp[i].add(temp+" "+s.substring(j,i));
                        }
                    }
                }
            }
        }
        return dp[dp.length-1];
    }