力扣HOT100(51) 动态规划-单词拆分

动态规划核心思路一句话讲透用dp[i]表示字符串s的前i个字符也就是s[0..i-1]能不能被字典里的单词拼接出来。对于每个位置i我们只需要找一个分割点j0 ≤ j i满足两个条件前j个字符已经可以被拆分dp[j] true从j到i的子串s[j..i-1]正好在字典里只要存在这样一个j那么dp[i]就等于true。完整解题步骤 --哈希表 dp 遍历双循环一个i负责变量s 一个j负责遍历0-i的分割点 看所有分割的可能1. 预处理字典转成哈希集合为了快速判断一个子串是否在字典里我们先把wordDict转成unordered_set这样查找的时间复杂度是 O (1)比直接遍历数组快很多。2. 初始化 dp 数组数组长度s.size() 1因为要表示前 0 个到前 n 个字符共 n1 种状态所有元素初始化为false边界条件dp[0] true前 0 个字符就是空串空串不需要任何单词就能拼接出来所以是合法的这是所有推导的基础没有这个条件整个 dp 数组都会是 false3. 遍历计算 dp 数组外层循环i从1到s.size()表示当前要判断前i个字符能不能被拆分内层循环j从0到i-1枚举所有可能的分割点如果dp[j] true前 j 个字符合法并且子串s.substr(j, i-j)在字典里那么dp[i] true直接 break 内层循环只要找到一个合法的分割点就行4. 返回结果dp[s.size()]就是整个字符串能不能被拆分的答案。class Solution { public: bool wordBreak(string s, vectorstring wordDict) { //转为哈希表集合 unordered_setstring wordSet; for(string word : wordDict){ wordSet.insert(word); } //初始化dp数组 //dp[i]表示前i个字符能不能被拆分 int n s.size(); vectorbool dp(n1,false);//n1个数 初始值都是false dp[0] true;//边界条件 //遍历 for(int i 1;in;i){ //分割点 for(int j 0;ji;j){ if(dp[j] wordSet.count(s.substr(j,i-j))){ dp[i] true; break; } } } return dp[n]; } };