LeetCode 140 - Word Break II

作者 QIFAN 日期 2017-02-17
LeetCode 140 - Word Break II

原题链接: 140. Word Break II


题干

给定一个非空字符串 s ,和一个字典 dict ,将 s 按照字典中的单词分割(加空格),返回所有可能结果。

字典中无重复,且单词均为非空

思路

先做一些测试:

  1. 空格也可以作为字典元素
    "catsand dog"
    [" ","cats","and","sand","dog"]
    返回:[“cats and dog”]

  2. 字典为空,返回空集

直观的 DFS 动态规划。每次传入参数为:当前缓存 curr ,当前已完成的字符串 temp ,字符串 s ,位置 i ,字典 dict ,结果集 res 。从头遍历 s 。当到达位置 i ,curr += s[i] ,并递归 (curr, temp, s, i + 1, dict, res),再检查字典中是否存在 curr ,若存在,temp += curr + " " , curr = “” ,并递归。

当 i = s.length() (base case)

  • 若 temp 为空,说明没有符合的,直接返回。
  • 若 curr 为空,去掉 temp 的最后一个空格,加入 res
  • 若 curr 不为空,temp += curr ,加入 res

因为字典是个 List ,所以 contains 操作若是遍历是 $O(N)$ ,我采用排序然后类似二叉查找的方法。

这样子是 TLE 的,觉得应该还是 contains 操作的次数太多,改成不一个一个走,而是按照字典中单词的长度往前走。结果还是 TLE 。

这里可以优化的地方在于字典中可能会有很多相同前缀的,如果后一个与前一个前缀相同且前一个不行,那后一个肯定就不用考虑了。再改。TLE

四改,这次优化了检查方式,不用 startsWith ,而是用一个 preOffset 表示上一个单词遍历到的位置。如果前缀相同那就是接着,如果不同 preOffset 是 0 也就是从头比较。

最应该优化的地方其实应该是 memo,因为同一范围的 s 会计算好多遍,不应该不应该。memo 存储的是 substring(pos) 能够组成的 valid sentences。如果存在,则将当前 temp 加上所有结果,再放入 res 。终于过了。

代码:

public List<String> wordBreak(String s, List<String> wordDict) {
Collections.sort(wordDict);
Map<String, List<String>> memo = new HashMap<>();
return match(s, wordDict, memo);
}
private List<String> match(String s, List<String> wordDict, Map<String, List<String>> memo) {
if (memo.containsKey(s)) {
return memo.get(s);
} else {
List<String> subs = new ArrayList<String>();
for (String word: wordDict) {
if (s.startsWith(word)) {
if (s.length() == word.length()) {
subs.add(word);
break;
} else {
List<String> subsubs = match(s.substring(word.length()), wordDict, memo);
for (String subsub: subsubs) {
subs.add(word + " " + subsub);
}
}
}
}
memo.put(s, subs);
return subs;
}
}