leetcode 139. Word Break 、140. Word Break II

时间:2022-01-26 08:26:50

139. Word Break

字符串能否通过划分成词典中的一个或多个单词。

使用动态规划,dp[i]表示当前以第i个位置(在字符串中实际上是i-1)结尾的字符串能否划分成词典中的单词。

j表示的是以当前i的位置往前找j个单词,如果在j个之前能正确分割,那只需判断当前这j单词能不能在词典中找到单词。j的个数不能超过词典最长单词的长度,且同时不能超过i的索引。

初始化时要初始化dp[0]为true,因为如果你找第一个刚好匹配成功的,你的dp[i - j]肯定就是dp[0]。因为多申请了一个,所以dp中的i相当于s中的i-1。

s.substr(i-j,j)实际上是s.substr(i-j + 1 - 1,j),因为本身应该提取i - j +1,但因为dp位置比s多一个,所以还要-1。

class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int length = ;
for(string word : wordDict){
if(word.size() > length)
length = word.size();
}
vector<bool> dp(s.size() + ,false);
dp[] = true;
for(int i = ;i <= s.size();i++){
for(int j = ;j <= length && j <= i;j++){
if(dp[i-j]){
string str = s.substr(i-j,j);
for(string word : wordDict){
if(word == str){
dp[i] = true;
break;
}
}
}
}
}
return dp[s.size()];
}
};

140. Word Break II

一个字符串加空字符串还是原字符串

class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_map<string, vector<string>> m;
return helper(s, wordDict, m);
}
vector<string> helper(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& m) {
if (m.count(s)) return m[s];
if (s == "") return {""};
vector<string> res;
for (string word : wordDict) {
if (s.substr(, word.size()) != word) continue;
vector<string> rem = helper(s.substr(word.size()), wordDict, m);
for (string str : rem) {
res.push_back(word + (str.empty() ? "" : " ") + str);
}
}
m[s] = res;
return res;
}
};

leetcode 139. Word Break 、140. Word Break II的更多相关文章

  1. python如何转换word格式、读取word内容、转成html

    # python如何转换word格式.读取word内容.转成html? import docx from win32com import client as wc # 首先将doc转换成docx wo ...

  2. leetcode 79&period; Word Search 、212&period; Word Search II

    https://www.cnblogs.com/grandyang/p/4332313.html 在一个矩阵中能不能找到string的一条路径 这个题使用的是dfs.但这个题与number of is ...

  3. 139&period; Word Break 以及 140&period;Word Break II

    139. Word Break Given a non-empty string s and a dictionary wordDict containing a list of non-empty  ...

  4. leetcode 127&period; Word Ladder、126&period; Word Ladder II

    127. Word Ladder 这道题使用bfs来解决,每次将满足要求的变换单词加入队列中. wordSet用来记录当前词典中的单词,做一个单词变换生成一个新单词,都需要判断这个单词是否在词典中,不 ...

  5. leetcode 1&period;Two Sum 、167&period; Two Sum II - Input array is sorted 、15&period; 3Sum 、16&period; 3Sum Closest 、 18&period; 4Sum 、653&period; Two Sum IV - Input is a BST

    1.two sum 用hash来存储数值和对应的位置索引,通过target-当前值来获得需要的值,然后再hash中寻找 错误代码1: Input:[3,2,4]6Output:[0,0]Expecte ...

  6. leetcode 169&period; Majority Element 、229&period; Majority Element II

    169. Majority Element 求超过数组个数一半的数 可以使用hash解决,时间复杂度为O(n),但空间复杂度也为O(n) class Solution { public: int ma ...

  7. leetcode 55&period; Jump Game、45&period; Jump Game II(贪心)

    55. Jump Game 第一种方法: 只要找到一个方式可以到达,那当前位置就是可以到达的,所以可以break class Solution { public: bool canJump(vecto ...

  8. leetcode 54&period; Spiral Matrix 、59&period; Spiral Matrix II

    54题是把二维数组安卓螺旋的顺序进行打印,59题是把1到n平方的数字按照螺旋的顺序进行放置 54. Spiral Matrix start表示的是每次一圈的开始,每次开始其实就是从(0,0).(1,1 ...

  9. leetcode 263&period; Ugly Number 、264&period; Ugly Number II 、313&period; Super Ugly Number 、204&period; Count Primes

    263. Ugly Number 注意:1.小于等于0都不属于丑数 2.while循环的判断不是num >= 0, 而是能被2 .3.5整除,即能被整除才去除这些数 class Solution ...

随机推荐

  1. Position和anchorPoint

    Main.storyboard ViewController.m // //  ViewController.m //  7A12.position和anchorPoint // //  Create ...

  2. OpenTSDB介绍——基于Hbase的分布式的,可伸缩的时间序列数据库,而Hbase本质是列存储

    原文链接:http://www.jianshu.com/p/0bafd0168647 OpenTSDB介绍 1.1.OpenTSDB是什么?主要用途是什么? 官方文档这样描述:OpenTSDB is ...

  3. 浏览器中显示视频,flash等的代码处理

    window.flashView=function(flash_url){ var html=''; html+='<div id="obj_flash_div">'; ...

  4. A Knight&&num;39&semi;s Journey

    poj2488:http://poj.org/problem?id=2488 题意:给你一张地图,然后有一个骑士,骑士可以从地图的任意一个方格开始,作为起点,问你该骑士能否走遍整张题图.题解:首先想到 ...

  5. UILabel的size根据文字的长短变化

     UILabel *label = [[UILabel alloc] init]; label.backgroundColor = [UIColor blackColor]; [self.view a ...

  6. 自动更改IP地址反爬虫*,支持多线程&lpar;转&rpar;

    8年多爬虫经验的人告诉你,国内ADSL是王道,多申请些线路,分布在多个不同的电信机房,能跨省跨市更好,我这里写好的断线重拨组件,你可以直接使用. ADSL拨号上网使用动态IP地址,每一次拨号得到的IP ...

  7. C&num;中函数的功能和类型

    函数  就是方法是独立完成某项功能的一个个体 函数的的三个好处:1.提高代码的重用性.2.提高功能开发的效率,3.提高代码的可维护性(主要功能). 函数也分为     固定功能函数(这类函数具有可封闭 ...

  8. Python &plus; Anaconda &plus; vscode环境重装(2019&period;4&period;20)

    目录 卸载程序 安装Ananconda 检查系统环境变量 更换国内镜像源 设置VS CODE 用户配置及工作环境配置 @(Python + Anaconda + vscode环境重装) 工程目录的使用 ...

  9. hadoop权威指南学习&lpar;一&rpar; - 天气预报MapReduce程序的开发和部署

    看过Tom White写的Hadoop权威指南(大象书)的朋友一定得从第一个天气预报的Map Reduce程序所吸引, 殊不知,Tom White大牛虽然在书中写了程序和讲解了原理,但是他以为你们都会 ...

  10. cygwin下如何运行crontab定时脚本&quest;

    1. 安装cron服务(如果不能启动,使用管理员身份运行cygwin) cygrunsrv -I cron -p /usr/sbin/cron -a -D -I 是安装 cron是服务名 -p /us ...