# Title: 140. Word Break II

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto 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 of solving problems

In fact, the solution of this problem is the same as 139. Word break. You can refer to the idea of 139. Word break https://my.oschina.net/JiamingMai/blog/4331735 , slightly different from 139. Word break, this question needs to record all the cases in which h [0] [i] is true.

# Time complexity analysis

In essence, it is the same as 139. Word break, so the time complexity is O (KN ^ 2), which is a reference for the analysis process https://my.oschina.net/JiamingMai/blog/4331735

# Finally realized

java implementation

``````public class Solution {

List<String&>[] records;

private boolean[][] h;

private boolean[][] r;

public List<String&> wordBreak(String s, List<String&> wordDict) {
int n = s.length();
if (!fastWordBreakInternal(s, wordDict)) {
return new ArrayList<&>();
}
boolean res = wordBreakInternal(s, wordDict);
if (res) {
return records[n];
}
return new ArrayList<&>();
}

public boolean fastWordBreakInternal(String s, List<String&> wordDict) {
int n = s.length();
h = new boolean[n+1][n+1];
r = new boolean[n+1][n+1];
initR(n, s, wordDict);
h[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i; j &>= 0; j--) {
if (!h[0][i]) {
h[0][i] = h[0][i-j] && r[i-j][i];
} else {
break;
}
}
}
return h[0][n];
}

public boolean wordBreakInternal(String s, List<String&> wordDict) {
int n = s.length();
h = new boolean[n + 1][n + 1];
r = new boolean[n + 1][n + 1];
records = new List[n + 1];
initR(n, s, wordDict);
h[0][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i; j &>= 0; j--) {
if (h[0][i - j] && r[i - j][i]) {
h[0][i] = true;
record(i, j, s);
}
}
}
return h[0][n];
}

private void record(int i, int j, String s) {
if (null == records[i]) {
records[i] = new ArrayList<&>();
}
String token = s.substring(i - j, i);
if (null != records[i - j]) {
for (String str : records[i - j]) {
StringBuffer sb = new StringBuffer();
sb.append(str).append(" ").append(token);
}
}  else {
}
}

private void initR(int n, String s, List<String&> wordDict) {
for (int i = 0; i <= n; i++) {
for (int j = i; j <= n; j++) {
r[i][j] = r(i, j, s, wordDict);
}
}
}

private boolean r(int i, int j, String s, List<String&> wordDict) {
String token = s.substring(i, j);
for (String word : wordDict) {
if (word.equals(token)) {
return true;
}
}
return false;
}

public static void main(String[] args) {
List<String&> wordDict = new ArrayList<&>();
String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
Solution solution = new Solution();
List<String&> res = solution.wordBreak(s, wordDict);
res.stream().forEach(str -&> {System.out.println(str);});
}

}
``````

note that in the main method of the code, the input is a continuous string of a with only one B in the middle. In this case, if you record while calculating directly, it will time out. So here’s a trick to quickly determine whether the input string can be disassembled. If not, you can directly output an empty list. This example is just a case that cannot be disassembled.