Comment on page

140.Word-Break-II

140. 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;
}
}