LeetCode 139. 【Java】139. Word Break
原题链接
中等
作者:
tt2767
,
2020-02-26 00:08:48
,
所有人可见
,
阅读 719
// 看来不同的dp想法,复杂度差很多啊
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet();
wordDict.forEach(set::add);
set.forEach(System.out::println);
// return dpRegion(s, set);
return dpLine(s, set);
}
/* O(n^3)
1. 状态定义: f[i][j] 表示 i~j 可以组成单词
2. 状态计算: 以第一个可以组成单词的结尾划分, 如果 i~k 和 k+1 ~j 都可以组成, 那么 i~j 就可以
可以时置为true, 不可以置为fasle
3. 边界条件: f[~][~] = None
*/
public boolean dpRegion(String s, Set<String> wordDict){
int n = s.length();
Boolean[][] f = new Boolean[n+1][n+1];
for (int len = 1 ; len <= n; len++){
for (int i = 1 ; i + len - 1 <= n; i++){
int j = i + len - 1;
f[i][j] = wordDict.contains(s.substring(i-1, j));
if (f[i][j] == true) continue;
for (int k = i; k < j; k++){
f[i][j] = f[i][j] || (f[i][k] && f[k+1][j]);
}
}
}
return f[1][n];
}
/* O(n^2)
1. 状态定义: f[i] 以i结尾的句子可以被组成
2. 状态计算: 以i结尾的单词划分, 如果单词前也是ok的那么以j结尾是ok的
3. 边界条件: f[~] = false, f[0] = true;
*/
public boolean dpLine(String s, Set<String> wordDict){
int n = s.length();
boolean[] f = new boolean[n+1];
f[0] = true;
for (int i = 1 ; i <= n ; i++){
for (int j = i; j <= n; j++){
f[j] = f[j] || (f[i-1] && wordDict.contains(s.substring(i-1, j)));
// 可优化的点
if (f[j] && j == n) return true;
}
}
return f[n];
}
}