第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0139. 单词拆分

题目地址(139. 单词拆分)

题目描述

1
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
2
3
说明:
4
5
拆分时可以重复使用字典中的单词。
6
你可以假设字典中没有重复的单词。
7
示例 1:
8
9
输入: s = "leetcode", wordDict = ["leet", "code"]
10
输出: true
11
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
12
示例 2:
13
14
输入: s = "applepenapple", wordDict = ["apple", "pen"]
15
输出: true
16
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
17
注意你可以重复使用字典中的单词。
18
示例 3:
19
20
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
21
输出: false
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题是给定一个字典和一个句子,判断该句子是否可以由字典里面的单词组出来,一个单词可以用多次。
暴力的方法是无解的,复杂度极其高。 我们考虑其是否可以拆分为小问题来解决。 对于问题(s, wordDict) 我们是否可以用(s', wordDict) 来解决。 其中 s' 是 s 的子序列, 当 s'变成寻常(长度为 0)的时候问题就解决了。 我们状态转移方程变成了这道题的难点。
我们可以建立一个数组 dp, dp[i]代表 字符串 s.substring(0, i) 能否由字典里面的单词组成,经过这样的抽象我们就可以建立 dp[i - word.length] 和 dp[i] 的关系。它们有什么关系?又该如何转移呢?
我们用图来感受一下:
139.word-break-1
没有明白也没有关系,我们分步骤解读一下:
(以下的图左边都代表 s,右边都是 dict,灰色代表没有处理的字符,绿色代表匹配成功,红色代表匹配失败)
139.word-break-2
139.word-break-3
139.word-break-4
139.word-break-5
上面分步解释了算法的基本过程,下面我们感性认识下这道题,我把它比喻为 你正在往一个老式手电筒🔦中装电池
139.word-break-6

代码

代码支持: JS,CPP
JS Code:
1
/**
2
* @param {string} s
3
* @param {string[]} wordDict
4
* @return {boolean}
5
*/
6
var wordBreak = function (s, wordDict) {
7
const dp = Array(s.length + 1);
8
dp[0] = true;
9
for (let i = 0; i < s.length + 1; i++) {
10
for (let word of wordDict) {
11
if (word.length <= i && dp[i - word.length]) {
12
if (s.substring(i - word.length, i) === word) {
13
dp[i] = true;
14
}
15
}
16
}
17
}
18
19
return dp[s.length] || false;
20
};
Copied!
CPP Code:
1
class Solution {
2
public:
3
bool wordBreak(string s, vector<string>& dict) {
4
unordered_set<string> st(begin(dict), end(dict));
5
int N = s.size();
6
vector<bool> dp(N + 1);
7
dp[0] = true;
8
for (int i = 1; i <= N; ++i) {
9
for (int j = 0; j < i && !dp[i]; ++j) {
10
dp[i] = dp[j] && st.count(s.substr(j, i - j));
11
}
12
}
13
return dp[N];
14
}
15
};
Copied!
复杂度分析
令 S 和 W 分别为字符串和字典的长度。
  • 时间复杂度:$O(S ^ 3)$
  • 空间复杂度:$O(S + W)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。