单词拆分

描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

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

示例 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 中的所有字符串 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这是一道经典的动态规划问题。我们可以使用 dp 数组来记录字典中的单词能否组成字符串 s 的前 i 个字符。其中 dp[i] 表示字符串 s 的前 i 个字符是否可以被字典中的单词拆分组成。因此我们需要遍历字符串 s 的所有子串，判断这些子串是否能够被字典中的单词拆分组成。

具体来说，我们可以从字符串 s 的第一个字符开始，枚举字符串 s 的所有子串。假设当前枚举到了字符串 s 的第 i 个字符，我们需要判断 s 的前 i 个字符是否可以被拆分成字典中的一个或多个单词。为此，我们可以枚举拆分位置 j，其中 j<i，并判断 s 的前 j 个字符组成的子串是否可以被拆分成字典中的一个或多个单词，以及 s[j+1,i] 是否在字典中出现。如果两个条件都满足，那么字符串 s 的前 i 个字符就可以被拆分成字典中的一个或多个单词，否则不能。

如果我们令 dp[i] 表示字符串 s 的前 i 个字符是否可以被字典中的单词拆分组成，则可以得到如下的状态转移方程：

dp[i] = dp[j] && check(s[j+1,i])

其中 check(s[j+1,i]) 表示子串 s[j+1,i] 是否在字典中出现。

最终，我们只需要返回 dp[n] 即可，其中 n 是字符串 s 的长度。

C++代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end()); // 使用哈希表存储字典中的单词
        int n = s.size();
        vector<bool> dp(n+1, false); // dp数组，dp[i]表示字符串s的前i个字符是否可以被字典中的单词拆分组成
        dp[0] = true; // 初始化状态
 
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && dict.count(s.substr(j, i-j))){ // 如果s的前j个字符可以被字典中的单词拆分组成，且s[j+1,i]在字典中出现 i-1-j+1 = i-j
                    dp[i] = true; // 则s的前i个字符可以被字典中的单词拆分组成
                    break; // 退出当前循环
                }
            }
        }

        return dp[n]; // 返回状态dp[n]
    }
};