Fork me on GitHub

Word Break

题目介绍

LeetCode 139. Word Break,原题的意思给定一个非空的字符串和非空的单词字典(不包含重复元素),判断字符串是否可以被分割成字典中的一个或者多个单词。

这题有进阶的题目,题解 Word Break II

解题思路

这是一题典型的动态规划,如果一个单词存在一种分解方法,分解后每一单词都应该在字典中,那必定满足一个条件:对于该单词的最后一个分割点,分割点到单词末尾的字符串是一个单词,而这个分割点到单词开头所组成的字符串也是可分解的。所以只要验证满足这个条件,我们则可以确定字符串是可分解的。

  1. 用外层循环来控制待验证的字符串的长度,而用内层的循环来寻找这么一个分割点,可以把字符串分成一个单词和一个同样可分解的子字符串。
  2. 同时,我们用数组记录下字符串长度递增时可分解的情况,以供之后使用,避免重复计算。用 Bool wordArray[i] 表示到字符串 s 的第 i 个字符时,是否可以用 wordDict 中的单词来表示。
  3. 假设有 wordArray[0…i-1] 的结果,那么 wordArray[i] 的值应该是:wordArray[i] = wordArray[j] && s.substring(j, i) in wordDict,其中 j 属于[0…i-1]。

时间复杂度 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
class Solution {
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
if s.isEmpty {
return true
}
if wordDict.count == 0 {
return false
}
var wordArray = Array.init(repeating: false, count: s.count + 1)
wordArray[0] = true
for i in 1...s.count {
for j in stride(from: i-1, through: 0, by: -1) {
if wordArray[j] && wordDict.contains(String(s[s.index(s.startIndex, offsetBy: j)..<s.index(s.startIndex, offsetBy: i)])) {
wordArray[i] = true
break
}
}
}
return wordArray[s.count]
}
}

版权声明



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/14/WordBreak/