139. 单词拆分
一句话套路dp[i]=前 i 个能否拆成词典词(布尔背包)
题目描述
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意,你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示:
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
思路
时间
O(n·L²)(L = 最长词长;内层 substr 拼接 + 哈希本身就要 O(L))空间
O(n)状态
dp[i] = s[0..i) 能否被拆成词典里的词。
转移
dp[i] = OR over j<i of (dp[j] && wordSet.count(s[j..i)))。
把「能不能拆」当成布尔背包:词典是物品,位置是容量。
优化
只枚举长度不超过词典最长词长的 j,复杂度从 O(n^2 · 匹配) 降到 O(n·L·匹配)。
想真拿到 O(n·L)
把词典装进 Trie(Q208)沿字符下走,戒掉 substr。
变体
Q140 要输出所有句子 -> 先跑本 DP 判可达,再从 n 反向 DFS 拼答案。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0139 {
class Solution {
public:
bool wordBreak(const string& s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
size_t maxLen = 0;
for (const string& w : dict) maxLen = max(maxLen, w.size());
const int n = (int)s.size();
vector<bool> dp(n + 1, false);
dp[0] = true; // 空串可拆
for (int i = 1; i <= n; ++i)
for (int j = max(0, i - (int)maxLen); j < i; ++j) // 只回看 maxLen 个位置
if (dp[j] && dict.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
return dp[n];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0139::Solution s;
vector<string> a{"leet", "code"};
CHECK_TRUE(s.wordBreak("leetcode", a));
vector<string> b{"apple", "pen"};
CHECK_TRUE(s.wordBreak("applepenapple", b));
vector<string> c{"cats", "dog", "sand", "and", "cat"};
CHECK_FALSE(s.wordBreak("catsandog", c));
vector<string> d{"car", "ca", "rs"};
CHECK_TRUE(s.wordBreak("cars", d)); // ca + rs(不是 car)
vector<string> e{"a"};
CHECK_TRUE(s.wordBreak("aaaa", e));
CHECK_TRUE(s.wordBreak("", e)); // 空串:什么都不拆就已满足(跟 dp[0]=true 一致)