HHot 100C++ 图解

139. 单词拆分

中等 动态规划(一维) 3 帧动画 在力扣上做

一句话套路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 <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 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 拼答案。

图解

j0 i0 a
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/15_dp.cpp20 行
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];
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q139_word_break12 行
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 一致)

↑↓ 选择↵ 打开/ 随时唤起