Fork me on GitHub

Word Break II

题目介绍

LeetCode 140. Word Break II,题目的意思原题的意思给定一个非空的字符串和非空的单词字典(不包含重复元素),将所有可能的分割方式用数组输出。

解题思路

记忆化搜索,在搜索过程中,使用字典tokenDict将已经搜索过的子句的拆解方案记录下来,从而实现DFS的剪枝。

时间复杂度 O(n²),空间复杂度 O(n²)。

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
class Solution {
func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
var cache = [String: [String]]()
return DFS(s, wordDict, &cache)
}
func DFS(_ s: String, _ wordDict: [String], _ cache: inout [String: [String]]) -> [String] {
if s.count == 0 {
return [""]
}
if let value = cache[s] {
return value
}
var result = [String]()
for word in wordDict {
if s.hasPrefix(word) {
let subWordBreaks = DFS(String(s.suffix(from: word.endIndex)), wordDict, &cache)
for subWordBreak in subWordBreaks {
if subWordBreak.isEmpty {
result.append(word)
} else {
result.append(word + " " + subWordBreak)
}
}
}
}
cache[s] = result;
return result;
}
}

版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/10/15/WordBreakII/