LeetCode 139 - Word Break

作者 QIFAN 日期 2017-01-07
LeetCode 139 - Word Break

原题链接: 139. Word Break


题干

给定一个非空字符串 s ,和一个 wordDict ,里面包括一组非空字符串。 判断 s 能否由一个或多个 wordDict 中的元素构成。

举例 1
s = “leetcode”
dict = [“leet”, “code”]

返回 true 。
解释:”leet” + “code” = “leetcode”

举例 2
s = “leetleet”
dict = [“leet”, “code”]

返回 true

思路

使用一个数组 res ,长度为 s.length() + 1res[i] 表示 s.substring(0, i) 能否由一个或多个 wordDict 中的元素构成。

以 s = “hij” , dict = [“hi”, “ij”, “hij”] 为例。

res[0] = true。因为若 wordDict 含有整串字符,应该返回 true 。
res[1] = res[0] && wordDict 里含有 "h" = false 。**不能构成 h **
res[2] = res[1] && wordDict 里含有 "i" (`false`)
|| res[0] && wordDict 里含有 "hi"(`true`) = true。**能构成 hi **
res[3] = res[2] && wordDict 里含有 "j" (`false`)
|| res[1] && wordDict 里含有 "ij" (`false`)
|| res[0] && wordDict 里含有 "hi" (`true`) = true。**能构成 hij **

最终结果为 true

核心等式为:

res[i] = (res[i] && wordDict.contains(s.substring(i, i + 1))
|| (res[i - 1] && wordDict.contains(s.substring(i - 1, i + 1)))
...
|| (res[0] && wordDict.contains(s.substring(0, i + 1)))

时间复杂度 worst case 为 $O(n^3)$
空间复杂度为 $O(n)$

代码:

public boolean wordBreak(String s, List<String> wordDict) {
if (wordDict == null || wordDict.size() == 0) {
return false;
}
int LENGTH = s.length();
boolean[] res = new boolean[LENGTH + 1];
// 初始化第一个
res[0] = true;
for (int pos = 0; pos < LENGTH; pos++) {
for (int k = pos; k >= 0; k--) {
// 能构成 0 ~ i = 能构成 0 ~ k && 字典中含有 k ~ i (0 <= k <= i)
res[pos + 1] = res[pos + 1] || (res[pos - k] && contains(wordDict, s.substring(pos - k, pos + 1)));
if (res[pos + 1]) {
break;
}
}
}
return res[LENGTH];
}
public boolean contains(List<String> wordDict, String item) {
for (String e: wordDict) {
if (item.equals(e)) {
return true;
}
}
return false;
}

Can we do better?
在这个思路下,我觉得在 contains 里面可以优化时间,如果把 list 变成 map 应该会快很多。