【Hot 100 刷题计划】 LeetCode 139. 单词拆分 | C++ 动态规划 (完全背包思维)

LeetCode 139. 单词拆分 题目描述题目级别中等给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。示例 1:输入:s leetcode,wordDict [leet, code]输出:true解释: 返回true因为leetcode可以由leet和code拼接成。示例 2:输入:s applepenapple,wordDict [apple, pen]输出:true解释: 返回true因为applepenapple可以由apple pen apple拼接成。注意你可以重复使用字典中的单词。 破题思路动态规划 / 完全背包模型这道题可以看作是一个特殊的完全背包问题背包总容量字符串的长度n。物品字典wordDict中的单词。物品重量单词的长度。使用限制每个单词可以无限制重复使用。但与普通背包不同的是字符串的拼接是有严格顺序要求的。因此我们在两层循环的遍历顺序上必须是外层遍历背包容量字符串前缀长度内层遍历物品字典中的单词。状态定义定义dp[i]为字符串s的前i个字符即长度为i的前缀能否利用字典中的单词拼接而成。状态转移方程对于当前长度为i的前缀我们遍历字典中的每一个单词wordDict[j]。如果当前前缀的长度i大于等于单词长度sz并且以i结尾的子串刚好和这个单词匹配s.substr(i - sz, sz) wordDict[j]那么当前长度i能否拼成就取决于**“刨去这个单词后剩下的前置长度i - sz能否拼成”**。dp[i] dp[i] || dp[i - sz]初始化dp[0] 1或true。代表长度为 0 的空字符串是可以被拼成的不需要任何单词。这是整个 DP 状态接力传递的起跑点 C 代码实现 (完全保留作者原版)classSolution{public:boolwordBreak(string s,vectorstringwordDict){intns.size(),mwordDict.size();// 开辟 DP 数组长度为 n 10 防止越界intdp[n10];// 初始化全部为 0 (false)memset(dp,0,sizeofdp);// 边界条件长度为 0 的前缀默认拼写成功作为接力的起点dp[0]1;// 外层循环遍历背包容量即字符串前缀的长度 ifor(inti0;in;i){// 内层循环遍历物品即字典中的所有单词for(intj0;jwordDict.size();j){intszwordDict[j].size();// 状态转移的前提当前前缀长度足够容纳该单词且尾部子串与单词完全匹配if(iszs.substr(i-sz,sz)wordDict[j]){// 只要找到一种合法的拆分方式dp[i] 就置为 1 (true)dp[i]dp[i]||dp[i-sz];}}}// 返回整个字符串长度 n 是否能被拼接成功returndp[n];}};