-
Notifications
You must be signed in to change notification settings - Fork 3
/
_0139_WordBreak.java
86 lines (79 loc) · 2.74 KB
/
_0139_WordBreak.java
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
77
78
79
80
81
82
83
84
85
86
package com.diguage.algorithm.leetcode;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* = 139. Word Break
*
* https://leetcode.com/problems/word-break/[Word Break - LeetCode]
*
* Given a *non-empty* string s and a dictionary wordDict containing a list of *non-empty* words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
*
* *Note:*
*
* * The same word in the dictionary may be reused multiple times in the segmentation.
* * You may assume the dictionary does not contain duplicate words.
*
* .Example 1:
* [source]
* ----
* Input: s = "leetcode", wordDict = ["leet", "code"]
* Output: true
* Explanation: Return true because "leetcode" can be segmented as "leet code".
* ----
*
* .Example 2:
* [source]
* ----
* Input: s = "applepenapple", wordDict = ["apple", "pen"]
* Output: true
* Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
* Note that you are allowed to reuse a dictionary word.
* ----
*
* .Example 3:
* [source]
* ----
* Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
* Output: false
* ----
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-24 09:39
*/
public class _0139_WordBreak {
/**
* Runtime: 11 ms, faster than 6.65% of Java online submissions for Word Break.
*
* Memory Usage: 44.3 MB, less than 5.08% of Java online submissions for Word Break.
*
* Copy from: https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode/[单词拆分 - 单词拆分 - 力扣(LeetCode)]
*/
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
Arrays.fill(dp, false);
dp[0] = true;
Set<String> dict = new HashSet<>(wordDict);
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
public static void main(String[] args) {
_0139_WordBreak solution = new _0139_WordBreak();
boolean r4 = solution.wordBreak("aaaaaaa", Arrays.asList("aaaa", "aaa"));
System.out.println(r4);
boolean r1 = solution.wordBreak("leetcode", Arrays.asList("leet", "code"));
System.out.println(r1);
boolean r2 = solution.wordBreak("applepenapple", Arrays.asList("apple", "pen"));
System.out.println(r2);
boolean r3 = solution.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat"));
System.out.println(!r3);
}
}