Repository navigation
Expand file tree
/
Copy pathAllConstructString.java
More file actions
65 lines (54 loc) · 2.16 KB
/
Copy pathAllConstructString.java
File metadata and controls
65 lines (54 loc) · 2.16 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package DSA.Dynamic;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
// combinatorics problem
// return 2d array of elements
public class AllConstructString {
public static void main(String[] args) {
System.out.println(allConstruct("abcdef", new String[]{"ab", "abc", "cd", "def", "abcd", "ef"}));
}
private static List<List<String>> allConstruct(String target, String[] words) {
if (target.isEmpty()) {
return new ArrayList<>(Collections.singletonList(new ArrayList<>()));
}
List<List<String>> result = new ArrayList<>();
for (String word : words) {
if (target.startsWith(word)) {
String suffix = target.substring(word.length());
List<List<String>> suffixWays = allConstruct(suffix, words);
for (List<String> way : suffixWays) { // add word to each level
List<String> newCombination = new ArrayList<>(way);
newCombination.add(word);
result.add(newCombination);
}
}
}
return result;
}
private static final Map<String, List<List<String>>> memo = new HashMap<>();
private static List<List<String>> allConstructMemo(String target, String[] words) {
if (target.isEmpty()) {
return new ArrayList<>(Collections.singletonList(new ArrayList<>()));
}
if (memo.containsKey(target)) {
memo.get(target);
}
List<List<String>> result = new ArrayList<>();
for (String word : words) {
if (target.startsWith(word)) {
String suffix = target.substring(word.length());
List<List<String>> suffixWays = allConstructMemo(suffix, words);
for (List<String> way : suffixWays) { // add word to each level
List<String> newCombination = new ArrayList<>(way);
newCombination.add(word);
result.add(newCombination);
}
}
}
memo.put(target, result);
return result;
}
}