140.Word-Break-II.md

140. Word Break II

---

题目地址

https://leetcode.com/problems/word-break-ii/

题目描述

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"
]

代码

Approach 1: Recursion with memoization

Complexity Analysis

• Time complexity : O_(_n^3). Size of recursion tree can go up to n^2. The creation of list takes n time.
• Space complexity : O(n^3).The depth of the recursion tree can go up to n and each activation record can contains a string list of size n.

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashMap<Integer, List<String>> memo = new HashMap();
        
        return dfs(s, 0, wordDict, memo);
    }
    
    private List<String> dfs(String s, Integer start, List<String> wordDict, HashMap<Integer, List<String>> memo) {
        if (memo.get(start) != null) {
            return memo.get(start);
        }
        List<String> ans = new LinkedList();
        if (start == s.length()) {
            ans.add("");
            return ans;
        }
        
        for (String word: wordDict) {
            for (int end = start + 1; end <= s.length(); end++) {
                String w = s.substring(start, end);
                if (word.equals(w)) {
                    
                    List<String> list = dfs(s, end, wordDict, memo);
                    for (String str: list) {
                        String seq = word + (str.length() > 0 ? " " : "") + str;
                        ans.add(seq);
                    }
                    
                }
            }
        }
        memo.put(start, ans);
        return ans;
    }
}

Approach #3 Using Dynamic Programming (Time Limit Exceeded)

Complexity Analysis

• Time complexity : O_(_n^3). Two loops are required to fill dp array and one loop for appending a list .
• Space complexity : O(n^3). Length of dp array is n and each value of dp array contains a list of string i.e. n^2 space.

class Solution {
  public List<String> wordBreak(String s, Set<String> wordDict) {
    LinkedList<String>[] dp = new LinkedList[s.length() + 1];
    LinkedList<String> initial = new LinkedList();
    initial.add("");
    dp[0] = initial;
    for (int i = 1; i <= s.length(); i++) {
      LinkedList<String> list = new LinkedList<>();
      for (int j = 0; j < i; j++) {
        if (dp[j].size() > 0 && wordDict.contains(s.substring(j, i))) {
          for (String l : dp[j]) {
            String w = l + (l.equals("") ? "" : " ");
            list.add(w + s.substring(j, i));
          }
        }
      }
      dp[i] = list;
    }

    return dp[s.length()];
  }
}

Fixed the DP solution, no "Time Limit Exceeded" :)

class Solution {
  public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    // Check if there is at least one possible sentence
    boolean[] dp1 = new boolean[s.length() + 1];
    dp1[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp1[j] && wordSet.contains(s.substring(j, i))) {
                dp1[i] = true;
                break;
            }
        }
    }

    // We are done if there isn't a valid sentence at all
    if (!dp1[s.length()]) {
        return new ArrayList<String>();
    }

    // Build the results with dynamic programming
    LinkedList<String>[] dp = new LinkedList[s.length() + 1];
    LinkedList<String> initial = new LinkedList<>();
    initial.add("");
    dp[0] = initial;
    for (int i = 1; i <= s.length(); i++) {
        LinkedList<String> list = new LinkedList<>();
        for (int j = 0; j < i; j++) {
            if (dp[j].size() > 0 && wordSet.contains(s.substring(j, i))) {
                for (String l : dp[j]) {
                    list.add(l + (l.equals("") ? "" : " ") + s.substring(j, i));
                }
            }
        }
        dp[i] = list;
    }
    return dp[s.length()];
  }
}

Approach #3 : Backtrace

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

  List<String> backtrace(String s, List<String> wordDict, HashMap<String, LinkedList<String>> map) {
    if (map.containsKey(s))    return map.get(s);

    LinkedList<String> res = new LinkedList<String>();
    if (s.length() == 0) {
      res.add("");
      return res;
    }

    for (String word : wordDict) {
      if (s.startsWith(word)) {
        List<String> sublist = backtrace(s.substring(word.length()), wordDict, map);
        for (String sub : sublist) {
          res.add(word + (sub.isEmpty() ? "" : " ") + sub);
        }
      }
    }

    map.put(s, res);
    return res;
  }
}