leetcod题:139. 单词拆分(中等)

2024-03-15 15:58
文章标签 中等 单词 139 拆分 leetcod

本文主要是介绍leetcod题:139. 单词拆分(中等),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述: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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

1、使用动态规划,dp[i]记录0~i的字符子串是否能被空格拆分成词典中存在一个或者多个的单词。

2、dp数组长度等于原始字符串长度,所有单位初始化为0

3、动态方程

如果j == 0 则,dp[i] == is_in_dict,这里is_in_dict表示j~i之间的字符子串是否存在词典中。

如果j>0则,dp[i]  = dp[j-1] && is_in_dict

4、根据动态方程,遍历元素字符串i,同时对每个i以 j=i倒序遍历,计算dp[i] = dp[j-1] && is_in_dict ,其中is_in_dict的计算就是判断s.substr(j,i-j+1)是否在词典中存在。

 

三、代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();set<string> wordSet;for(auto it = wordDict.begin();it != wordDict.end();it++){wordSet.insert(*it);}if(len == 1){if (wordSet.find(s) != wordSet.end())return true;elsereturn false;}vector<int> dp(len,0);dp[0] = 0;for (int i = 0;i<len;i++){for(int j = i;j>=0;j--){string tmp = s.substr(j,i-j+1);auto it = wordSet.find(tmp);if (it != wordSet.end()){/*cout<<"tmp:"<<tmp<<endl;cout<<"j="<<j<<endl;cout<<"i="<<i<<endl;*/if(j == 0){dp[i] = 1;continue;}if(dp[j-1] == 1){dp[i] = dp[j-1];break;}// cout<<"dp[j]="<<dp[j-1]<<endl;// cout<<"********************"<<endl;}}}// printt(dp);return dp[len-1];}void printt(vector<int> & dp){cout<<"print:";for(int i = 0; i<dp.size();i++){cout<<dp[i];}cout<<endl;}
};

 

 

这篇关于leetcod题:139. 单词拆分(中等)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/812490

相关文章

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【中等】保研/考研408机试-二分查找(模板题)

二分查找就是在一个有序数组中查找某个值,以首端尾端的中点mid查找对比,mid与要查找的数进行对比,看落在哪个区间,在那个区间重新得到首端和尾端,进而得到新的mid值。 一、模板题 二分查找-I_牛客题霸_牛客网 class Solution {public:int search(vector<int>& nums, int target) {int left=0,right=nums.s

隐私计算实训营:SplitRec:当拆分学习遇上推荐系统

拆分学习的概念 拆分学习的核心思想是拆分网络结构。每一个参与方拥有模型结构的一部分,所有参与方的模型合在一起形成一个完整的模型。训练过程中,不同参与方只对本地模型进行正向或者反向传播计算,并将计算结果传递给下一个参与方。多个参与方通过联合模型进行训练直至最终收敛。 一个典型的拆分学习例子: Alice持有数据和基础模型。Bob只有数据、基础模型和fuse模型。 Alice使用自己的数据

动态规划---单词拆分

题目: 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 思路:本题属于完全背包问题,字符串s的长度为背包容量,字符串列表wordDict中的每一个元素相当于物品。 动态规划五部曲: 1.确定dp数组及含义 dp数组为元素类型是布

WPS如何查看已添加到词典的单词

WPS Office(12.1.0.17827) ① 点击文件,在文件中找到选项 ② 找到拼写检查并点击自定义词典 ③ 如果要删除已添加到词典的"错词",则点击修改 ④ 选择"错词", 点击删除

Java中等题-整数替换(力扣)

给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2替换 n 。如果 n 是奇数,则可以用 n + 1或n - 1替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 输入:n = 8输出:3解释:8 -> 4 -> 2 -> 1 示例 2: 输入:n = 7输出:4解释:7 -> 8 -> 4 -> 2 -> 1或 7 ->

Java中等题-摆动序列(力扣)

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一

【C】单词长度

课程:程序设计入门——C语言(翁恺) 题目内容: 你的程序要读入一行文本,其中以空格分隔为若干个单词,以‘.’结束。你要输出这行文本中每个单词的长度。这里的单词与语言无关,可以包括各种符号,比如“it's”算一个单词,长度为4。注意,行中可能出现连续的空格。 输入格式: 输入在一行中给出一行文本,以‘.’结束,结尾的句号不能计算在最后一个单词的长度内。 输出格式: 在一行中输出这行

代码随想录第八天|151.翻转字符串里的单词 卡码网:55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串

反转字符串的单词 思路:刷过稍微忘记 class Solution {public://去除空格string remove(string s){//使用快慢指针int slow=0;int i=0;for(;i<s.size();i++){if(s[i]!=' '){if(slow!=0){s[slow++]=' ';}while(s[i]!=' '&&i<s.size()){s[slow+

Java中等题-递增的三元子序列(力扣)

你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。 示例 1: 输入:nums = [1,2,3,4,5]输出:true解释:任何 i < j < k 的三元组都满足题意