DP专题17 单词拆分

本题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目：

思路：

? ? ? ? 由题意，根据题目意思，给出字符串 S，以及一个字符串数组，问字符串数组中??? 是否可以任取字符串拼成字符串 S。

? ? ? ? 根据这个题目，我们可以看成完全背包问题，又因为我们选取的字符串??可以不在乎顺序的进行选取，所以我们用 排列数的遍历方式，总结下来：? 完全背包问题+排列数遍历方式

? ? ? ? 第一步，确定dp[i] 的含义。

? ? ? ? 这里题目要求的是判断是否可以拼成字符串 S，

????????所以我们 dp 数组可以为 bool 类型的dp数组，

????????当 dp [ 结果含义下标 ] 返回真就是真，返回假就是假

????????其中 dp[ i ] 下标? i 的含义我们得要确定好。

? ? ? ? 我们根据正常思维去联想? ?提取的字符串S 的片段? ?的进行判断是否存在我们的字符串数组，

其中提取字符串 S 的片段的时候，有一个因素就是 片段 S 的长度。

? ? ? ? 所以我们可以将?dp[ i ] 下标? i 的含义定义为 字符串长度。

? ? ? ? 当 我们 dp[ S.lenght() ] = true 的时候就是有真结果，反之。

? ? ? ? 综上所述，我们确定好了 dp[ i ] 的全部含义了.

? ? ? ? dp[ i ]? 为 我们求是否 可以拼成 S 的结果，? ?i? 为 字符串长度

? ? ? ? 第二步，确定 dp公式

? ? ? ? 根据总结下来：? 完全背包问题+排列数遍历方式

? ? ? ? 这里? ?背包容量，我们可以是? S 的长度，问 '物品' 字符串选取S片段 是否符合，并且长度可以凑成 背包容量 ,既可以。

? ? ? ? 详细遍历过程如下：

????????????????

// 排列数遍历，先遍历背包容量，再遍历物品
for(int i = 1;i <= S.size();++i)    // S 目标拼凑成的字符串长度
{
    for(int j = 0;j < i;++j)    // 选取物品片段长度
    {
         string word = s.substr(j,i - j);    // 这里是选取字符串片段

    }
}

? ? ? ? 确定好 dp 整个过程后，逻辑也开始清晰起来，当 我们截取的 S 字符串片段存在的时候，并且我们之前凑成的 dp[ j ] 也存在的时候，说明 当前 i 是可以凑成的。

? ? ? ? dp 公式如下：? ?dp[ i ] = bool (wordDict.find(word) == true and dp[ j ]);?

? ? ? ? 这里可能有点疑惑，为什么要 dp [ j ] 判断，解释如下：

????????

第三步，确定dp 初始化

? ? ? ? 由 第二步 我们整个? dp? 已经得到清晰的逻辑了，我们是根据 截取的字符串长度进行拼凑递推下去，直到得到结果。其中遍历顺序有个特点，就是? 我们遍历字符串 S 长度的时候为什么 不是?

for(int i = 0;i <= s.size();++i)

这里就是我们 dp 初始化的关键， 我们就是? dp[ 0 ] = true? 的初始化

我们为什么要 dp[ 0 ] = true 的初始化，就是因为 我们可以将 空字符串 也当作是截取的一个片段，我们空串是肯定存在的，视作为可以拼凑成的， 其它的我们得需要根据?wordDict 的存在情况进行实际的拼凑。 所以? dp[ 0 ] = true ,其它为 false

代码详解如下：

class Solution {
public:
    unordered_set<string>st; // 用于查新判断截取字符串存在情况
    bool wordBreak(string& s, vector<string>& wordDict) {
        for(string &i:wordDict) st.emplace(i);   // 提前哈希存储好我们 wordDict 存在哪些 字符串
        int len = s.size(); // 计算字符串长度
        vector<bool>dp(len + 2,false);  // 定义 截取长度字符串 dp  bool数组
        dp[0] = true;   // dp 初始化，空字符串是 true
        
        // 开始完全背包，排列数遍历法遍历 dp
        for(int i = 1;i <= len;++i) // '背包' S 字符串长度
        {
            if(dp[i]) continue;    // 小优化
            for(int j = 0;j < i;++j)    // 截取字符串的 下标
            {
                if(!dp[j]) continue;    // 小优化
                string word = s.substr(j,i - j);    // 截取字符串
                if(st.find(word) != st.end() and dp[j]) dp[i] = true; // dp 公式
            }
        }
        return dp[len]; // 返回结果
    }
};

最后提交：