LeetCode刷题笔记——T0139 单词拆分

题目描述：

题目思路：

本题属于背包问题，构建dp数组：vector dp(s.size()+1, false)。dp[i]数组的含义可以理解为：当往背包中放入字符串s的前i个字符时，是否能够由字典中的单词拼接而成。对dp数组进行初始化：dp[0]=true，当背包中不放入字符时，肯定可以由字典中的单词拼接构成，即不放入字典中的单词即可。

将字符串列表中的单词放入容器unordered_set dict(wordDict.cbegin(), wordDict.cend())，以便于查找。然后将字符串s中的前i个字符，逐次放入背包，找出前i个字符以字符s[i]为终止位置的所有子串（设子串长度为j小于等于i）。当子串可以在字典中被找到，且字符串s的前i-j个字符可以被字典中的单词拼接而成，则表示字符串的前i个字符可以被字典中的单词拼接而成。

代码如下：

    class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());
            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) {
                    string word = s.substr(j, i - j);
                    if (dict.find(word) != dict.end() && dp[j])
                        dp[i] = true;
                }
            }
            return dp[s.size()];
        }
    };

提交结果：

本题题解思路来源于：代码随想录