后端 leetcode 140. word break ii

morangeman · May 28, 2020 · 3 hits

140. Word Break II

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;
}
}
No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.