140. Word Break 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:
[]

Thinking:

• Method 1: MLE
  • DP,将每一个字符位可能出现的结果都通过List保存起来，后面的结果是根据前面的结果而来的。

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String>[] dp = new List[s.length() + 1];
        int len = s.length();
        dp[0] = new ArrayList<>();
        if(len == 0) return dp[0];
        Set<Integer> set = new HashSet<>();
        for(String ss : wordDict)
            set.add(ss.length());
        for(int i = 1; i <= len; i++){
            dp[i] = new ArrayList<>();
            for(Integer in : set){
                if(i - in >= 0){
                    String sub = s.substring(i - in, i);
                    if(wordDict.contains(sub)){
                        List<String> tmp = dp[i - in];
                        if(i - in == 0)
                            dp[i].add(sub);
                        else{
                            for(String ss : tmp){
                                dp[i].add(ss + " " + sub);
                            }
                        }
                    }
                }
            }
        }
        return dp[len];
    }
}

• Method 2: dp + 递归

class Solution {
    Map<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> result = new ArrayList<>();
        if(s.length() == 0){
            result.add("");
            map.put("", result);
            return result;
        }
        for(String word : wordDict){
            if(s.startsWith(word)){
                List<String> subWords = wordBreak(s.substring(word.length()), wordDict);
                for(String subWord : subWords)
                    result.add(word + (subWord.length() > 0 ? " ":"") + subWord);
            }
        }
        map.put(s, result);
        return result;
    }
}

二刷

1. 通过回溯。 TLE

   class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new LinkedList<>();
        backtrace(s, wordDict, new StringBuilder(), result);
        return result;
    }
    private void backtrace(String s, List<String> wordDict, StringBuilder sb, List<String> result){
        if(sb.toString().replace(" ", "").length() == s.length())
            result.add(sb.toString());
        else{
            String cur = sb.toString().replace(" ", "");
            for(String ss : wordDict){
                if(s.startsWith(cur + ss)){
                    StringBuilder temp = null;
                    if(cur.length() == 0)
                        temp = new StringBuilder(sb.toString() + ss);
                    else
                        temp = new StringBuilder(sb.toString() + " " + ss);
                    backtrace(s, wordDict, temp, result);
                }
            }
        }
    }
   }
   

2. 通过DP， TLE

   class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new LinkedList<>();
        int len = s.length();
        List[] dp = new List[len + 1];
        dp[0] = new LinkedList<String>();
        dp[0].add("");
        for(int i = 1; i <= len; i++){
            for(String word : wordDict){
                int wordLen = word.length();
                if(i - wordLen >= 0 && dp[i - wordLen] != null){
                    if(s.substring(i - wordLen, i).equals(word)){
                        if(dp[i] == null) dp[i] = new LinkedList<String>();
                        List<String> temp = dp[i - wordLen];
                        for(String ss : temp){
                            if(ss.length() == 0) dp[i].add(word);
                            else dp[i].add(ss + " " + word);
                        }
                    }
                }
            }
        }
        return dp[len];
    }
   }
   

3. DP + 递归， 思路是通后往前遍历。因为添加了递归，所以我们要用一个外部变量去保存dp，所以选择了map。这道题参考了一刷时候的结果。

   class Solution {
    Map<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> result = new LinkedList<>();
        if(s.length() == 0){
            result.add("");
            map.put("", result);
            return result;
        }
        for(String word : wordDict){
            if(s.startsWith(word)){
                List<String> res = wordBreak(s.substring(word.length()), wordDict);
                for(String ss : res){
                    result.add(word + (ss.length() == 0 ? "": " ") + ss);
                }
            }
        }
        map.put(s, result);
        return result;
    }
   }