DP专题17 单词拆分

原创于 2024-01-22 21:38:03 发布 · 粉丝可见 · 895 阅读 · 13 · 20 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135757999

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

题目：

思路：

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

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

第一步，确定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 长度的时候为什么不是

1	`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]; // 返回结果
    }
};