企业官网建设流程全解析

12380网站建设打算,马鞍山什么房产网站做的好,学做宝宝衣服网站,最有效的网站推广方法题目回顾#xff1a;Word Break 是在问什么#xff1f; 题目给定#xff1a; 一个字符串 s#xff1b;一个字符串数组 wordDict#xff0c;表示字典。 要求#xff1a; 判断 s 能不能被拆分成若干个单词#xff0c;这些单词都必须来自 wordDict#xff0c;并且可以重…题目回顾Word Break 是在问什么题目给定一个字符串s一个字符串数组wordDict表示字典。要求判断s能不能被拆分成若干个单词这些单词都必须来自wordDict并且可以重复使用。leetcode​例如s leetcode,wordDict [leet, code]答案是true因为可以拆成 “leet code”。leetcode​s applepenapple,wordDict [apple, pen]答案是true可以拆成 “apple pen apple”。leetcode​s catsandog,wordDict [cats,dog,sand,and,cat]答案是false怎么拆都不行。leetcode​本题约束1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 1000。leetcode​初始思路dp[i]表示“前 i 个字母能否被拼出”一开始的直觉非常自然定义dp[i]表示前 i 个字符能不能由字典里的单词拼出来。用 C 字符串的说法就是判断s[0..i-1]这一段是不是可拆分。这是一个非常典型、也是正确的状态定义dp[0]对应“前 0 个字符”也就是空串dp[4]对应s[0..3]比如 “leet”dp[n]对应整个字符串s[0..n-1]。但是在这个定义下有两个关键点一开始容易踩坑dp[0]应该是true还是false匹配一个单词时要不要把“单词中间的 dp 位置”也标记为true下面按这些疑问一点点展开。核心概念前缀和“前缀结束点”理解这题 DP 的关键是把i看成一个“前缀结束点”。什么是前缀对字符串s applepen“a”、“ap”、“apple”、“applep”……都叫s的前缀。一般说“长度为 i 的前缀”指的是s[0..i-1]。什么是前缀结束点从下标的角度看字符的下标是0..n-1切割位置有n1个开头的 0字符之间的位置1..n-1和最后结尾的n。把dp[i]定义成dp[i] true表示在切割位置i把字符串切一刀左边s[0..i-1]这一整段已经可以完全由字典单词拼出来。换句话说i就是一个“可行前缀的结束点”。这有两个重要含义dp[i] true的下标i才有资格作为“下一个单词的起点”单词中间的那些位置比如 “leet” 的 1、2、3不能作为“前面那段已经完整拼完”的位置所以dp[1],dp[2],dp[3]不应该被设为true。为什么dp[0]必须是truedp[0]表示前 0 个字符空串能不能被“若干个字典单词”拼出来。这里有一个常见约定空串可以看作由“0 个单词”拼出来。也就是不选任何单词结果就是空串。这样做的好处是把下标 0 当作第一个“可行前缀结束点”为后面的第一个单词提供一个起点。例如在 “leetcode” 里如果dp[0] true并且s[0..3] leet就可以把dp[4]设为true这表示 “leet” 可以被拼出来。如果dp[0] false那从 0 开始永远扩展不出任何true状态整个 DP 直接挂掉。顺带一提本题的约束保证s.length 1不会出现空串输入。leetcode​如果从数学上扩展这道题让s 绝大多数人会认为答案应为true空串可以由 0 个单词组成也和dp[0] true的建模是一致的。注意这里不是说“字典里有一个空串单词”而是说“空前缀是一种已经完成的状态”。转移逻辑只从true的位置向后扩展在状态和dp[0]搞清楚之后转移的思想可以归结成一句话只从那些dp[i]为true的位置出发尝试往后贴单词更新新的前缀结束点。更具体地说状态dp[i]表示s[0..i-1]是否可拆分。初始化dp[0] 1true其余为 0false。leetcode​转移外层遍历i从 0 到str_len - 1如果dp[i] 0说明前缀s[0..i-1]还拼不出来直接continue不能从这里起步。leetcode​如果dp[i] 1说明这里是一个“可行前缀结束点”可以尝试从这里往后贴单词。内层遍历字典中的每个word记word_len strlen(word)。leetcode​如果i word_len str_len说明这个单词贴过去会越界跳过。leetcode​否则比较子串如果s[i..iword_len-1]恰好等于这个word例如用strncmp(s i, word, word_len) 0说明从i出发接上这个单词可以安全到达位置i word_len所以将dp[i word_len] 1。leetcode​结束整个字符串长度为str_len如果dp[str_len] 1表示前str_len个字符也就是整个s可以被完全拆分返回true否则返回false。leetcode​这就是你最后写出的那份 C 代码的完整逻辑分配dp[strlen(s) 1]memset(dp, 0, ...)全部初始化为 0dp[0] 1两层循环做扩展返回dp[str_len]。leetcode​“单词中间的dp值”为什么保持为false一开始你有一个想法匹配一个单词以后从i到ilen中间的dp都设为true。现在可以清晰地看到这样做是错的。原因有两个1. 语义不对dp[k]的语义是前 k 个字符能否被“完全拆完”。如果从 0 匹配 “leet” 到 4只能说明前 4 个字符 “leet” 是可拆的也就是dp[4] true。不应该得出“dp[1],dp[2],dp[3]也都可拆”的结论因为 “l”、“le”、“lee” 并没有被字典单词完全覆盖。2. 会制造错误的起点如果把dp[1..3]都设为true后续在这些位置继续贴单词会创建出实际不存在的拆分路径。例如在复杂的例子中这可能会让算法认为某个拆法是可行的但其实中间断掉了。正确的做法就是只更新单词末尾那个位置从i匹配长度为len的单词只把dp[i len]置为true。单词内部的位置保持false这样循环走到这些位置时看到dp[k] 0就会“自然跳过”。和常见“背包形式”的关系你提到过想用常见的“背包 DP 模板”来表达背包中常见形式dp[j] max(dp[j], dp[j - w[i]] v[i])在 Word Break 里可以做一个类比j对应“前缀结束点”w[i]对应“某个单词的长度len”没有价值v[i]只关心“能否到达”。逻辑上可以写成对每个 j1..n 对每个单词 word长度 len 如果 j - len 0dp[j-len] true并且 s[j-len..j-1] word 则 dp[j] dp[j] || dp[j - len] 实际上就是 dp[j] true。和“max 写法”的对比把 “max” 换成 “||”逻辑或表示“存在一种方案就行”把 “dp[j - w[i]] v[i]” 换成了“dp[j-len]且子串匹配成功”。不过在实际写代码时这种“模板形态”的形式不如直接写if更直观所以最后代码通常还是如果dp[i]为 1 且s[i..iword_len-1] word就dp[i word_len] 1。完整思路小结把上面的内容压缩成一个“拿来就能用”的解题框架1. 定义状态dp[i]前 i 个字符s[0..i-1]能否被字典单词完全拆分。2. 初始化dp[0] true表示空前缀已经是一个合法拆分其他位置初始为false。3. 状态转移遍历i从 0 到n-1如果dp[i] false跳过这个位置不能作为起点。否则枚举字典中的每个单词wordlen word.length()若i len n且s[i..ilen-1] word则dp[i len] true。4. 答案看dp[n]是否为truen是s.length。用一句话概括把每个dp[i] true的位置看成图中的一个点从这里出发用字典单词当边一条条跳到新的位置i len(word)最后看能不能跳到位置n。你提交的那份 C 代码正是完整实现了这一套逻辑并在 LeetCode 上通过了所有测试用时 0ms说明理解已经非常扎实。leetcode​相关链接Word Break - LeetCode 题目描述Word Break - LeetCode 提交记录