尧图网络科技YAOTU DIGITAL 获取报价
获取报价
首页 / 资讯中心 / 文章详情

单词拆分的动态规划解法

发布时间:2026/9/28 20:57:30

资讯中心
01
ARTICLE

单词拆分的动态规划解法

单词拆分的动态规划解法
139. 单词拆分 - 力扣LeetCode给你一个字符串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 拼接成。 注意你可以重复使用字典中的单词。示例 3输入:s catsandog, wordDict [cats, dog, sand, and, cat]输出:false解题思路定义dp[i]表示字符串s的前 i 个字符即子串s[0..i-1]能否由字典中的一个或多个单词拼接而成。显然dp[0] true表示空串可以被拼出作为递推的起点。对于i从 1 到nn s.length()我们枚举最后一个单词的起始位置 j0 ≤ j i如果dp[j] true说明前j个字符已经能拼出并且子串s[j..i-1]也出现在字典中那么前i个字符就能拼出即dp[i] true。dp[j]wordDictSet.contains(s.substring(j,i)动态规划五部走1. 状态表示dp[i]表示字符串s的前 i 个字符即子串s[0..i-1]能否由字典中的一个或多个单词拼接而成。2. 状态转移方程dp[i] true当且仅当存在某个 j0 ≤ j i使得dp[j] true 且 s[j..i-1] 在 wordDict 中3. 初始化dp[ 0 ] true 表示空字符串在字典中4. 填表顺序由于dp[i]只依赖下标比i小的状态所以可以从前往后依次填表5. 返回值dp[ s.length() ]class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString wordDictSet new HashSet(wordDict); boolean[] dp new boolean[s.length()1]; dp[0] true; for(int i1;is.length();i){ for(int j0;ji;j){ if(dp[j]wordDictSet.contains(s.substring(j,i))){ dp[i] true; break; } } } return dp[s.length()]; } }
02
RELATED NEWS

相关资讯

更多网站建设与数字化升级内容

03
WHY YAOTU

想打造同款高转化官网?

懂行业、懂生意,从建站到增长一站式陪跑

◈

场景化定制

不做模板站,围绕你的业务场景量身设计,小众不撞款。

◐

营销型架构

以转化目标组织内容与路径,让官网真正带来询盘。

▲

全周期服务

设计、开发、运营、运维一体,上线只是开始。

免费获取你的建站方案

留下需求,专属顾问 24 小时内为你输出方案建议。