跳转至

139. 单词拆分

力扣链接(中等)：https://leetcode.cn/problems/word-break

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

Text Only
1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

Text Only
1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

Text Only
1
2
输入: 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 中的所有字符串 互不相同

个人题解

建议完成 494. 目标和 和 416. 分割等和子集 后再完成本题。

  1. dp[j] 表示区间为 [0, j] 的子串是否可以由字典中出现的一个或多个单词拼接而成；
  2. 递推关系：如果当前单词 wordDict[i] 与字符串 s 区间 [j - wordDict[i].size(), j] 相等，并且字符串 s 除当前单词外的前一段子串 dp[j - wordDict[i].size()] == true，那么显然 dp[j] = true，即区间为 [0, j] 的子串可以由字典中的单词拼接；
  3. 初始化 dp[0] = true，很明显，一个长度为 0 的子串，可以由任何字典拼接；
  4. 由题可知，字典中的单词可以重复使用，属于完全背包问题；又 ab 可以由 a + b 拼接，但不能由 b + a 拼接，依赖物品选择的顺序，属于排列问题。遍历顺序：外层遍历背包容量，内层遍历物品项，且从前向后遍历；
  5. 手动推导 dp 数组无误。
C++
 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
28
29
30
31
32
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 要使得 dict 能够按顺序组合成字符串 s
        // 可以转换为用 dict 中的物品，装满背包 s
        const int N = 1010;
        bool dp[N] = {};

        dp[0] = true;

        // 因为题目要求必须按顺序拼接，所以这是一个排列问题
        // 注意 size() 返回无符号 size_t，如果计算产生负数，会导致溢出
        for(int j = 1; j <= s.size(); j++) {
            for(int i = 0; i < wordDict.size(); i++) {
                if(j < wordDict[i].size()) continue;
                auto word = s.substr(j - wordDict[i].size(), wordDict[i].size());  // (begin, length)
                if(wordDict[i] == word && dp[j - wordDict[i].size()]) dp[j] = true;
            }
        }

        // 其他写法
        // unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        // for(int j = 1; j <= s.size(); j++) {
        //     for(int i = 0; i < j; i++) {
        //         auto word = s.substr(i, j - i);  // (begin, length)
        //         if(wordSet.find(word) != wordSet.end() && dp[i]) dp[j] = true;
        //     }
        // }

        return dp[s.size()];
    }
};