单词划分2

给定一个非空字符串 s 和一个包含非空单词列表的字典
wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明： 分隔时可以重复使用字典中的单词；你可以假设字典中没有重复的单词。

示例 1：

输入: s = “catsanddog” wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
输出: [ “cats and dog”, “cat sand dog” ]

示例 2：

输入: s = “pineapplepenapple” wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
输出: [“pine apple pen apple”, “pineapple pen apple”,“pine applepen apple”]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog” wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: []

回溯法

class Solution {
    //hashmap存已经求得的，提高效率
    Map<String,List<String>> map = new HashMap<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        //存储每一种情况的结果
        List<String> res=new ArrayList<>();
        //字符串已经为空
        if(s.isBlank()){
            res.add("");
            return res;
        }

        //map中已经存入s的字符串
        if(map.containsKey(s))
            return map.get(s);
        
        for(String word:wordDict){
            //若s开头的单词在wordDict中存在
            if(s.startsWith(word)){
                //截取开头以后的s，进行递归
                List<String> tmpList=wordBreak(s.substring(word.length()),wordDict);
                for(String tmp:tmpList){
                    res.add(word+(tmp.equals("")?"":" "+tmp));
                }        
            }
        }
        map.put(s,res);
        return res;
    }
}