题目
LeetCode.139.单词拆分（中等）
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
题解
解法1：递归
提到拆分，我们可以考虑能不能把大问题拆分为子问题+有限步骤，给问题建模，简化讨论。
- 如果s可以被拆分，那么至少s的末尾字符组成的单词肯定是在wordDict中的。
- s的末尾字符组成的单词，可以从s的末尾位置开始，依次穷举取长度为1、2、3……n的子字符串，看子字符串是否在wordDict中。
- 接下来再去看剩下的前半部分的子字符串能不能继续拆分成功。
- 如果s不能被拆分，有两种情况:
- 穷举s所有末尾子字符串，是没有一个子字符串是在wordDict中的。
- 末尾有一部分子字符串组成的单词在wordDict中，最后s剩下前半段的子字符串不能被wordDict拆分。
这里已经划分出了子问题+有限步骤，可以用递归来解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
fun wordBreak(s: String, wordDict: List<String>): Boolean {
fun canBreak(end: Int): Boolean {
if (end < 0) return true
var result = false
for (start in end downTo 0) {
val tailString = s.substring(start, end + 1)
if (wordDict.contains(tailString)) {
result = canBreak(start - 1) || result
}
}
return result
}
return canBreak(s.length - 1)
}
}
|
解法2：记忆化递归
递归的问题在于有重叠子问题，有很多重复计算耗时，保存一下中间计算结果就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
fun wordBreak(s: String, wordDict: List<String>): Boolean {
val memo = IntArray(s.length) { -1 }
fun canBreak(end: Int): Boolean {
if (end < 0) return true
if (memo[end] != -1) {
return if (memo[end] == 1) true else false
}
var result = false
for (start in end downTo 0) {
val tailString = s.substring(start, end + 1)
if (wordDict.contains(tailString)) {
result = canBreak(start - 1) || result
}
}
memo[end] = if (result) 1 else 0
return result
}
return canBreak(s.length - 1)
}
}
|
解法3：自下而上递推式动态规划
能用记忆化递归的，也可以用自下而上递推的方式做。
设dp[end]为第0个到第end个字符组成的字符串是否可以被wordDict中的单词拆分。
穷举所有s[0, end]的末尾字符串，判断能否拆分。
设s[0, end]的末尾字符串的开始索引为start，0 <= start <= end。
状态转移方程
dp[end] = dp[start - 1] && s[start, end] in wordDict
start==0 时，截取的是整个字符串，直接判断整个字符串是否在wordDict里就行了，dp[0] = s[start, end] in wordDict。
由于计算新的状态需要读取之前的每个最优化的状态，所以空间无法优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
fun wordBreak(s: String, wordDict: List<String>): Boolean {
val n = s.length
if (n == 0) return false
val dp = BooleanArray(n) { false }
for (end in 0 until n) {
for (start in 0..end) {
val word = s.substring(start, end + 1)
if (start == 0) {
if (word in wordDict) {
dp[end] = true
break
}
} else {
if (dp[start - 1] && word in wordDict) {
dp[end] = true
break
}
}
}
}
return dp[n - 1]
}
}
|