单词拆分II

Question

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:
[]

Solution

采用深度优先遍历（DFS）

采用DFS遍历所有情况，原理是用字典遍历字符串来判断是否可以拆分成字典+子字符串
如果可以进一步的递归拆分子字符串，知道字符串长度为空
最后返回的时候合并各种子字符串组合
这里还需要记录之前遍历字符串可以拆分的情况来提高效率，防止大数据测试时计算耗时殆尽

Runtime: 5 ms, faster than 96.12% of Java online submissions for Word Break II.
Memory Usage: 39.3 MB, less than 28.95% of Java online submissions for Word Break II.

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<String, LinkedList<String>> his = new HashMap<>();
        return dfs(s, wordDict, his);
    }

    private LinkedList<String> dfs(String s, List<String> wordDict, Map<String, LinkedList<String>> his) {
        if (his.containsKey(s)) return his.get(s);

        LinkedList<String> ret = new LinkedList<>();
        if (s.length() == 0) {
            ret.push("");
            return ret;
        }
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                LinkedList<String> subs = dfs(s.substring(word.length()), wordDict, his);
                for (String sub : subs) {
                    ret.push(word + (sub.isEmpty() ? "" : " ") + sub);
                }
            }
        }
        his.put(s, ret);
        return ret;
    }
}