WordBreak2

https://leetcode.com/problems/word-break-ii/
给定一个String，和一个Dict，Dict中包含些许英文单词，求这个String是否能被这个Dict中的所有单词拼接起来，即这个String的子串都在这个Dict中,返回所有拼接的可能结果集
注意，Dict中的单词没有重复，且Dict中的单词可以被重复利用
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]

WordBreak的升级版本wordBreak

解题思路

深度优先遍历

• helper function的解释，对于String S，和Dict， 满足需求的所有可能，返回一个List
• 与WordBreak类似，从左开始算单词是否在Dict中，如果

talk is cheap ，show me your example：

image.png

代码如下

public List<String> wordBreak222(String s, List<String> wordDict) {
        Map<String, List<String>> hash = new HashMap<String, List<String>>();
        return wordHelper(s, wordDict, hash);
    }

    public List<String> wordHelper(String s, List<String> wordDict, Map<String, List<String>> m) {
        if (m.containsKey(s)) {
            return m.get(s);
        }
        List<String> res = new ArrayList<String>();

        if (s.isEmpty()) {
            res.add("");
            return res;
        }


        for (String word : wordDict) {

            if (!s.startsWith(word)) {
                continue;
            }

            List<String> rem = wordHelper(s.substring(word.length()), wordDict, m);

            for (String str : rem) {
                res.add(word + (str == "" ? "" : " ") + str);
            }
        }
        m.put(s, res);
        return res;
    }