单词拆分(LeetCode-139)

简介: 单词拆分(LeetCode-139)

7. 单词拆分(LeetCode-139)


题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。


**注意:**不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。


示例 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


提示:


1 <= s.length <= 300

1 <= wordDict.length <= 1000

1 <= wordDict[i].length <= 20

s 和 wordDict[i] 仅有小写英文字母组成

wordDict 中的所有字符串 互不相同


思路

不会,卡尔哥的也没看懂。然后发现官方题解很清晰


我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程,每次转移的时候我们需要枚举包含位置 i-1 的最后一个单词,看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说,我们需要枚举 s[0~i-1] 中的分割点 j ,看 s[0~j-1] 组成的字符串 S 1 (默认 j = 0 时 S 1 为空串)和 s[j~i-1] 组成的字符串 S 2 S_2S 2 是否都合法,如果两个字符串均合法,那么按照定义 S 1和 S 22拼接成的字符串也同样合法。由于计算到 dp[i] 时我们已经计算出了 dp[0~i−1] 的值,因此字符串 S 1 是否合法可以直接由 dp[j] 得知,剩下的我们只需要看 S 2 是否合法即可,因此我们可以得出如下转移方程

d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )


五部曲


dp[i] 含义


表示字符串前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词

递推公式


d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )


数组初始化


dp[0]=true 表示字符串为空,但题目中说了“给定⼀个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。

遍历顺序


实在是没看懂,直接复制卡尔哥的原话了


题⽬中说是拆分为⼀个或多个在字典中出现的单词,所以这是完全背包。

还要讨论两层for循环的前后循序。

如果求组合数就是外层for循环遍历物品,内层for遍历背包。

如果求排列数就是外层for遍历背包,内层for循环遍历物品。

本题最终要求的是是否都出现过,所以对出现单词集合⾥的元素是组合还是排列,并不在意!

那么本题使⽤求排列的⽅式,还是求组合的⽅式都可以。

即:外层for循环遍历物品,内层for遍历背包 或者 外层for遍历背包,内层for循环遍历物品 都是可以的。


但本题还有特殊性,因为是要求⼦串,最好是遍历背包放在外循环,将遍历物品放在内循环。如果要是外层for循环遍历物品,内层for遍历背包,就需要把所有的⼦串都预先放在⼀个容器⾥。(如果不理解的话,可以⾃⼰尝试这么写⼀写就理解了)所以最终我选择的遍历顺序为:遍历背包放在外循环,将遍历物品放在内循环。内循环从前到后。


测试用例



代码展示

class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> wordset(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 0; i <= s.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end())
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};
目录
相关文章
|
10月前
|
自然语言处理 API
分词提取[关键词提取]免费API接口教程
接口用于从指定文本中提取关键词,支持POST和GET请求。需提供用户ID、用户KEY及待提取文本,可选设置关键词分隔符。返回状态码及结果或错误信息。示例中ID与KEY为公共测试用,建议使用个人ID与KEY以获得更高调用频率。
|
前端开发
视觉盛宴:用CSS渐变动画打造炫酷背景!
视觉盛宴:用CSS渐变动画打造炫酷背景!
|
C#
C# async await 异步执行方法
C# async await 异步执行方法
99 0
|
JavaScript 前端开发 UED
Vue:为什么要使用v-cloak
Vue:为什么要使用v-cloak
143 1
|
存储 缓存 前端开发
微机原理与接口技术 微处理器架构详解
本文主要详解微处理器的架构。从微处理器的分类开始,到微处理器的历史、冯·诺依曼结构、哈佛结构等进行了细致地分析与总结。
687 1
微机原理与接口技术 微处理器架构详解
为什么Vue2中出现data数据刷新但是视图不更新的问题,但是Vue3中没有
为什么Vue2中出现data数据刷新但是视图不更新的问题,但是Vue3中没有
|
缓存 前端开发
💡我居然用错了useMemo和useCallback这么久?
💡我居然用错了useMemo和useCallback这么久?
|
Linux Shell API
AndroidQ(10.0) 内核版本增加linux编译用户信息
AndroidQ(10.0) 内核版本增加linux编译用户信息
375 0
|
JavaScript 前端开发
鼠标移到某一元素则在元素旁边出现弹出框(JQuery)
类似于当当网的发货以后的那个发货反馈,鼠标移上去后自动会弹出一个框,位置随位置的改变而改变,代码如下:  DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.
1124 0
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1257 5