LeetCode hot 100—单词拆分

题目

给你一个字符串 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

分析

动态规划

初始化动态规划数组：

创建一个长度为 n + 1 的布尔型数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以由字典中的单词拼接而成。

初始化 dp[0] 为 true，因为空字符串可以由字典中的单词拼接而成。

将字典中的单词存入哈希集合：

使用 std::unordered_set 存储字典中的单词，这样可以在 \(O(1)\) 的时间复杂度内查找一个单词是否在字典中。

动态规划求解：

外层循环遍历字符串 s 的每个位置 i。

内层循环遍历从 0 到 i - 1 的每个位置 j。

如果 dp[j] 为 true，表示 s 的前 j 个字符可以由字典中的单词拼接而成，并且 s.substr(j, i - j) 是字典中的一个单词，则将 dp[i] 设为 true。

返回结果：

最终返回 dp[n]，表示字符串 s 是否可以由字典中的单词拼接而成。

时间复杂度：O()，  是字符串的长度

空间复杂度：O()

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        int n = s.length();
        // dp[i] 表示 s 的前 i 个字符是否可以由字典中的单词拼接而成
        std::vector<bool> dp(n + 1, false);
        dp[0] = true; // 空字符串可以由字典中的单词拼接而成
        // 将字典中的单词存入哈希集合，方便快速查找
        std::unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                // 如果 s 的前 j 个字符可以由字典中的单词拼接而成，并且 s[j, i-1] 是字典中的一个单词
                if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};