-
Notifications
You must be signed in to change notification settings - Fork 26
/
Problem139_wordBreak.java
137 lines (116 loc) · 4.15 KB
/
Problem139_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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package com.longluo.top100;
import java.util.Arrays;
import java.util.List;
/**
* 139. 单词拆分
* <p>
* 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
* 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
* <p>
* 示例 1:
* 输入: s = "leetcode", wordDict = ["leet", "code"]
* 输出: true
* 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
* <p>
* 示例 2:
* 输入: s = "applepenapple", wordDict = ["apple", "pen"]
* 输出: true
* 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
* 注意,你可以重复使用字典中的单词。
* <p>
* 示例 3:
* 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
* 输出: false
* <p>
* 提示:
* 1 <= s.length <= 300
* 1 <= wordDict.length <= 1000
* 1 <= wordDict[i].length <= 20
* s 和 wordDict[i] 仅有小写英文字母组成
* wordDict 中的所有字符串 互不相同
* <p>
* https://leetcode.com/problems/word-break/
*/
public class Problem139_wordBreak {
// DP time: O(n^2) space: O(n)
public static boolean wordBreak_dp(String s, List<String> wordDict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
for (String word : wordDict) {
if (s.startsWith(word)) {
dp[word.length()] = true;
}
}
for (int i = 0; i < len; i++) {
if (dp[i]) {
for (String word : wordDict) {
if (s.startsWith(word, i)) {
dp[i + word.length()] = true;
}
}
}
}
return dp[len];
}
// Trie Done
public static boolean wordBreak_trie(String s, List<String> wordDict) {
Trie root = new Trie();
for (String word : wordDict) {
root.insert(word);
}
return root.search(s, 0);
}
static class Trie {
public boolean isEnd;
public Trie next[];
boolean[] failed = new boolean[301];
public Trie() {
isEnd = false;
next = new Trie[26];
}
public void insert(String word) {
Trie node = this;
for (char ch : word.toCharArray()) {
int idx = ch - 'a';
if (node.next[idx] == null) {
node.next[idx] = new Trie();
}
node = node.next[idx];
}
node.isEnd = true;
}
public boolean search(String s, int start) {
if (failed[start]) {
return false;
}
if (start >= s.length()) {
return true;
}
Trie root = this;
Trie pNode = root;
int len = s.length();
for (int i = start; i < len; i++) {
int idx = s.charAt(i) - 'a';
if (pNode.next[idx] == null) {
return false;
}
pNode = pNode.next[idx];
if (pNode.isEnd) {
if (search(s, i + 1)) {
return true;
}
failed[i + 1] = true;
}
}
return false;
}
}
public static void main(String[] args) {
System.out.println("true ?= " + wordBreak_dp("leetcode", Arrays.asList(new String[]{"leet", "code"})));
System.out.println("true ?= " + wordBreak_dp("applepenapple", Arrays.asList(new String[]{"apple", "pen"})));
System.out.println("false ?= " + wordBreak_dp("catsandog", Arrays.asList(new String[]{"cats", "dog", "sand", "and", "cat"})));
System.out.println("false ?= " + wordBreak_trie("aaaa", Arrays.asList(new String[]{"aaa"})));
System.out.println("true ?= " + wordBreak_trie("leetcode", Arrays.asList(new String[]{"leet", "code"})));
System.out.println("false ?= " + wordBreak_trie("catsandog", Arrays.asList(new String[]{"cats", "dog", "sand", "and", "cat"})));
}
}