forked from dimitar9/Algorithm_Collection
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathT139_word_break.java
More file actions
36 lines (30 loc) · 921 Bytes
/
T139_word_break.java
File metadata and controls
36 lines (30 loc) · 921 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
30
31
32
33
34
35
36
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] f = new boolean[s.length() + 1];
Arrays.fill(f, false);
f[0] = true;
/* First DP
for(int i = 1; i <= s.length(); i++){
for(String str: dict){
if(str.length() <= i){
if(f[i - str.length()]){
if(s.substring(i-str.length(), i).equals(str)){
f[i] = true;
break;
}
}
}
}
}*/
//Second DP
for(int i=1; i <= s.length(); i++){
for(int j=0; j < i; j++){
if(f[j] && dict.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}
return f[s.length()];
}
}