-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathLeetCode139.java
More file actions
48 lines (43 loc) · 1.81 KB
/
Copy pathLeetCode139.java
File metadata and controls
48 lines (43 loc) · 1.81 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
package LeetCode.String;
import java.util.*;
public class LeetCode139 {
// dp解法
public boolean wordBreak(String s, List<String> wordDict){
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
// =============backtracking解法
public boolean wordBreak2(String s, List<String> wordDict) {
return backtracking(s, wordDict, 0, new boolean[s.length()]);
}
private boolean backtracking(String s, List<String> dict, int i, boolean[] unbreakable) {
if (i == s.length()) return true;
if (unbreakable[i]) return false;
for(String string : dict){
if (!s.startsWith(string, i)) continue;
if (backtracking(s, dict, i+string.length(), unbreakable)) return true;
}
unbreakable[i] = true;
return false;
}
public static void main(String[] args) {
LeetCode139 instance = new LeetCode139();
String[] arr = {"apple", "pen"};
String[] arr2 = {"cats", "dog", "sand", "and", "cat"};
String[] arr3 = {"a","b","bbb","bbbb"};
String[] arr4 = {"bc", "cb"};
String[] arr5 = {"a"};
String q = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
String[] arr6 = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
System.out.println(instance.wordBreak(q, Arrays.asList(arr6)));
}
}