单词拆分----dp

思路刚开始看的时候没有思路但我看给的样例可以多次遍历wordDict看。。。好像不太对准备看看题解。首先需要知道这道题的dp的公式代表这什么dp[i]表示 字符串s从起始位置到位置i能否被被拆分成字典中的单词可能是一个也可能是多个。比如dp[3]就是问s[1],s[2],s[3] 这三个字符能否拆分成字典中单词的组合。于是我们下一步需要思考一下代码应该怎么写class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString wset new HashSet(wordDict); int n s.length(); boolean[] dp new boolean[n 1]; dp[0] true; // 空字符串可以拼出来 for(int i 1;i n;i){ for(int j 0;j i;j){ if(dp[j] wset.contains(s.substring(j,i))){ dp[i] true; } } } return dp[n]; } }s.substring(a,b)中b是不包含的也就是说真实包含的数组下标是a-----b-1解释一下dp[0]为什么等于true,因为在拆分的时候s leetcodewordDict [leetcode]。当i 8内层循环j 0dp[0]为true并且s.substring(0, 8) leetcode在字典中 → 条件成立dp[8]true。如果没有dp[0]true那么即使整个字符串是一个单词也无法通过j0的情况识别出来所有以j0开头的判断都会失败导致错误结果。我们一步一步把if (dp[j] wordSet.contains(s.substring(j, i)))和dp[i] true之间的逻辑关系拆开讲清楚。1. 先明确dp数组的含义在这段代码中dp[k]表示原字符串s的前k个字符即s[0]到s[k-1]这一段能否被拆分成字典中的单词。例如dp[3]就是问s[0],s[1],s[2]这三个字符能否拆分成字典里的单词组合。2. 我们要算什么外层循环i从 1 到n是要依次判断dp[1],dp[2], …dp[n]是否为真。当我们在计算dp[i]时我们要问前i个字符能不能被拆分成字典里的单词一种思考方式是把前i个字符想象成“前面一段” “最后一段”。“前面一段”的长度是j0 ≤ j i也就是s[0..j-1]。“最后一段”就是从索引j到i-1的子串长度为i-j也就是s.substring(j, i)。如果能找到某个j使得前面一段(s[0..j-1]) 可以被拆分成字典单词即dp[j] true并且最后一段(s.substring(j, i)) 本身就在字典里wordSet.contains(...)那么整个s[0..i-1]就肯定可以被拆分前面一段按dp[j]的方式拆最后一段直接作为单词。3. 所以if条件里的dp[j] wordSet.contains(...)就是检查这个假设是否成立dp[j] true→ 前j个字符可拆分。s.substring(j, i)在字典里 → 从j到i-1这一段直接是一个单词。如果两者都满足那么s[0..i-1]就找到了一个拆分方案因此dp[i]应该为true。4. 为什么dp[i] true只写一次就够了因为一旦我们找到了一个有效的j就证明了dp[i]可以为true不需要继续找其他j反正结果已经是真了。所以代码里break跳出内层循环。5. 举个例子用具体数字帮助理解s leetcodewordDict [leet,code]。我们要算dp[8]整个字符串长度 8。内层循环j从 0 到 7当j 4时dp[4]是什么前面算过leet可拆分 →dp[4]true。s.substring(4, 8)是什么索引 4~7 →code在字典中。条件成立 → 给dp[8] true。这就是 “前 8 个字符可以拆成(前4个字符leet)(4..8code)”。总结一句话if (dp[j] wordSet.contains(s.substring(j, i)))就是在问“能不能把前i个字符切成两半使得前半部分可拆分dp[j]true后半部分本身就是一个单词在字典里”如果能那么dp[i]就是true。