Difficulty:: Hard
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:
1
2
3
4
5
6
7
8
|
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
|
Example 2:
1
2
3
4
5
6
7
8
9
10
|
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:
1
2
3
4
5
|
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]
|
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class {
public List<String> wordBreak(String s, List<String> wordDict) {
if (s == null || wordDict == null || s.length() == 0 || wordDict.size() == 0) {
return new ArrayList<>();
}
Set<String> wordSet = new HashSet<>(wordDict);
Map<Integer, List<String>> map = new HashMap<>();
return dfsHelper(s, 0, wordSet, map);
}
public List<String> dfsHelper(String s, int start, Set<String> wordSet, Map<Integer, List<String>> map) {
if (map.containsKey(start)) {
return map.get(start);
}
List<String> res = new ArrayList<>();
if (start >= s.length()) {
res.add("");
}
String cur;
for (int i = start; i < s.length(); i++) {
if (wordSet.contains((cur = s.substring(start, i + 1)))) {
List<String> following = dfsHelper(s, i + 1, wordSet, map);
for (String f : following) {
res.add(cur + (f.length() == 0 ? "" : " ") + f);
}
}
}
map.put(start, res);
return res;
}
}
|
