forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWord Break II.java
More file actions
29 lines (26 loc) · 793 Bytes
/
Word Break II.java
File metadata and controls
29 lines (26 loc) · 793 Bytes
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
class Solution {
Map<Integer, List<String>> map = new HashMap<>();
public List<String> wordBreak(String s, List <String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
return helper(s, set, 0);
}
private List<String> helper(String s, Set<String> set, int start) {
if (map.containsKey(start)) {
return map.get(start);
}
List<String> ans = new ArrayList <>();
if (start == s.length()) {
ans.add("");
}
for (int i = start + 1; i <= s.length(); i++) {
if (set.contains(s.substring(start, i))) {
List<String> list = helper(s, set, i);
for (String word : list) {
ans.add(s.substring(start, i) + (word.equals("") ? "" : " ") + word);
}
}
}
map.put(start, ans);
return ans;
}
}