LeetCode 140. Word Break II

[Woodyiiiiiii]

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. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

---

与139. Word Break不同，这道题要返回的是所有能够匹配的字符串集合，所以我们要遍历所有可能， 不能像基础题那样记忆化能否匹配就可以了。

用一个HashMap<String, List>结构来存储结构，值存储的是键字符串对应的能够匹配字典的结果字符串数组。显然这道题不能用DP，我们就用正常的递归+记忆化搜索思路。

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashMap<String, List<String>> map = new HashMap<>();
        return helper(s, wordDict, map);
    }
    public List<String> helper(String s, List<String> wordDict,
                               HashMap<String, List<String>> map) {
        if (map.containsKey(s)) return map.get(s);
        List<String> res = new ArrayList<>();
        if (s.isEmpty()) {
            res.add("");
            return res;
        }
        for (String word : wordDict) {
            if (word.length() > s.length()) continue;
            if (!(s.substring(0, word.length()).equals(word))) continue;
            List<String> list = helper(s.substring(word.length()), wordDict, map);
            for (String str : list)
                res.add(word + (str.isEmpty() ? "" : " ") + str);
        }
        map.put(s, res);
        return res;
    }
}

如果不想多用一个函数，可在单独函数内完。当然此时为了参数匹配(否则发生重载)，HashMap要被声明为全局属性。

class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (map.containsKey(s)) return map.get(s);
        List<String> res = new ArrayList<>();
        if (s.isEmpty()) {
            res.add("");
            return res;
        }
        for (String word : wordDict) {
            if (word.length() > s.length()) continue;
            if (!(s.substring(0, word.length()).equals(word))) continue;
            List<String> list = wordBreak(s.substring(word.length()), wordDict);
            for (String str : list)
                res.add(word + (str.isEmpty() ? "" : " ") + str);
        }
        map.put(s, res);
        return res;
    }
}

---

参考资料：

• https://leetcode.com/problems/word-break-ii/
• [LeetCode] 140. Word Break II grandyang/leetcode#140