力扣：139.单词拆分

力扣：139.单词拆分
题目：
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
做题感悟：
背包的含义，物品的含义，做题需要知道什么，其实代码随想录中已经有了步骤了，不光光是这五个大型的步骤，还有很多小的步骤，仿照它一步步来即可，就好比如说，开始它说了背包的含义，物品的含义，以及实现的目的学习它的思考流程，然后仿照。但是自己之前始终没有意识到。

背包：从完整字符串中选定的字符串
物品：选定的字符串中的单词

dp数组的含义：
dp[i] : 选定的的长度为i的字符串能否被组成

递归公式讲解：

• 你会将选定的字符串划分为两部分字符串，前一部分字符串通过dp来查看是否能被组成，后一部分字符串通过判断字典中是否含有这个单词来查看是否能被组成。整体来查看这个选定的字符串呢能否被组成。

初始化：
dp[0] = true

遍历顺序：
for（背包）for（物品）
此题需要明确知道 i 的含义，j 的含义，划分的前后字符串的下标范围，通过i，j的含义以及递归公式来确定i，j的范围
i：选定的字符串的长度，因此其范围为
j：选定的字符串中的单词的长度即前一部分字符串的长度，划分为两部分，前一部分的dp必须已知，所以 j 不能等于i 因此j的范围为0~i-1同时因为其范围为 0~i-1 所以 i 也可作为划分的界限下标值，若前部分字符串的长度为j，那么前部分字符串下标范围为0 ~j-1，后部分字符串的下标范围为j ~i-1。
代码：

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19