-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathwordBreak.java
More file actions
76 lines (72 loc) · 2.37 KB
/
wordBreak.java
File metadata and controls
76 lines (72 loc) · 2.37 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
66
67
68
69
70
71
72
73
74
75
76
import java.util.*;
/*
对于wordbreak I, II(一个是判断true/false 一个是找到所有的paths)
分别有两种方法可以做，一个是DP,一个是DF（with memorization）
这里是DFS方法
* */
public class wordBreak {
public static void main(String[] args){
wordBreak obj = new wordBreak();
String s= "leetcode";
List<String> wordDict = new ArrayList<>();
wordDict.add("leet");
wordDict.add("code");
wordDict.add("leetcode");
System.out.println(obj.wB(s, wordDict));
Set<String> words = new HashSet<>(wordDict);
System.out.println(obj.wB2(s, words));
}
// find true/false
public boolean wB(String s, List<String> wordDict){
Set<String> words = new HashSet<>(wordDict);
Map<String, Boolean> map = new HashMap<>();
return dfs(s, words, map);
}
private boolean dfs(String s, Set<String> words, Map<String, Boolean> map){
if(map.containsKey(s)){
return map.get(s);
}
if(words.contains(s)){
map.put(s, true);
return true;
}
if(s.length() == 1 && !words.contains(s)){
map.put(s, false);
return false;
}
for(int i = 1; i < s.length(); i++){
boolean left = dfs(s.substring(0,i), words, map);
boolean right = dfs(s.substring(i, s.length()),words, map);
if(left && right){
map.put(s, true);
return true;
}else{
map.put(s, false);
}
}
return false;
}
// find all paths
//map: string -> its results
Map<String, List<String>> map = new HashMap<>();
public List<String> wB2(String s, Set<String> words){
if(map.containsKey(s)){
return map.get(s);
}
List<String> res = new ArrayList<>();
if(s.length() == 0){
res.add("");
}
for(int i = 0; i < s.length(); i++){
if(words.contains(s.substring(i,s.length()))){
System.out.println(s.substring(i,s.length()));
List<String> pre = wB2(s.substring(0,i), words);
for(String e: pre){
res.add(e + (e.equals("")? "": " ") + s.substring(i,s.length()));
}
}
}
map.put(s,res);
return res;
}
}