代码随想录（单词拆分）

题目：

思路：

把问题看为，使用字典里的单词去组成字符串，其中字典里的单词视为物品，字符串视为背包，并且每个单词可以重复使用，因此这可以认为是一个完全背包问题。

首先明确dp数组的含义，对于dp[i],i为字符串的长度,dp[i]为是否可以组成，也就是为true或者false。

接下来确定递推公式，如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。这里递推公式的精髓在于可以取到单词组成字符串的前j个，即dp[j] = 1,；根据这个递推j以后的字符，即从j开始取字符直到i - j个可以凑成下一个字典里的单词，此时，字符串下标为i，即dp[i]=1。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

 单词拆分 //


class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());
        std::vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                std::string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

int main() {
    Solution solution;

    // 示例字符串和字典
    std::string s = "leetcode";
    std::vector<std::string> wordDict = {"leet", "code"};

    bool canBreak = solution.wordBreak(s, wordDict);
    
    if (canBreak) {
        std::cout << "The string \"" << s << "\" can be segmented." << std::endl;
    } else {
        std::cout << "The string \"" << s << "\" cannot be segmented." << std::endl;
    }

    return 0;
}

原文地址：https://blog.csdn.net/qq_46454669/article/details/142610527

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！