杭州商业空间设计公司_界面设计报价_安卓优化大师新版_定制网站+域名+企业邮箱

单词拆分

1、题目描述

题目链接：139. 单词拆分 - 力扣（LeetCode）

题目描述：

2、题目解答

思路和算法

总的来说，就是需要看到底如何定义这个状态转移函数dp，上述主要用到的方法就是借助于dp[i]为true，然后判断dp[j]的话直接就是只需要查找dp[i…j]是否在单词字典中就可以了

3、代码实现

class Solution
{
public:bool wordBreak(string s, vector<string> &wordDict){// 创建一个无序集合 wordDictSet，存储字典中的单词auto wordDictSet = unordered_set<string>();for (auto word : wordDict)wordDictSet.insert(word);  // 将单词添加到集合中// 创建一个布尔型数组 dp，初始化为 false，dp[0] 为 trueauto dp = vector<bool>(s.size() + 1);dp[0] = true;// 遍历字符串 s 的每个位置 ifor (int i = 1; i <= s.size(); i++){// 检查从 0 到 i 的所有子串for (int j = 0; j < i; j++){// 如果 dp[j] 为 true 且子串 s.substr(j, i - j) 在字典中if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()){// 更新 dp[i] 为 truedp[i] = true;// 找到符合条件的子串后，退出内层循环break;}}}// 返回 dp[s.size()]，即整个字符串 s 是否可以被拆分return dp[s.size()];}
};