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的更多相关文章
-
python如何转换word格式、读取word内容、转成html
# python如何转换word格式.读取word内容.转成html? import docx from win32com import client as wc # 首先将doc转换成docx wo ...
-
leetcode 79. Word Search 、212. Word Search II
https://www.cnblogs.com/grandyang/p/4332313.html 在一个矩阵中能不能找到string的一条路径 这个题使用的是dfs.但这个题与number of is ...
-
139. Word Break 以及 140.Word Break II
139. Word Break Given a non-empty string s and a dictionary wordDict containing a list of non-empty ...
-
leetcode 127. Word Ladder、126. Word Ladder II
127. Word Ladder 这道题使用bfs来解决,每次将满足要求的变换单词加入队列中. wordSet用来记录当前词典中的单词,做一个单词变换生成一个新单词,都需要判断这个单词是否在词典中,不 ...
-
leetcode 1.Two Sum 、167. Two Sum II - Input array is sorted 、15. 3Sum 、16. 3Sum Closest 、 18. 4Sum 、653. Two Sum IV - Input is a BST
1.two sum 用hash来存储数值和对应的位置索引,通过target-当前值来获得需要的值,然后再hash中寻找 错误代码1: Input:[3,2,4]6Output:[0,0]Expecte ...
-
leetcode 169. Majority Element 、229. Majority Element II
169. Majority Element 求超过数组个数一半的数 可以使用hash解决,时间复杂度为O(n),但空间复杂度也为O(n) class Solution { public: int ma ...
-
leetcode 55. Jump Game、45. Jump Game II(贪心)
55. Jump Game 第一种方法: 只要找到一个方式可以到达,那当前位置就是可以到达的,所以可以break class Solution { public: bool canJump(vecto ...
-
leetcode 54. Spiral Matrix 、59. Spiral Matrix II
54题是把二维数组安卓螺旋的顺序进行打印,59题是把1到n平方的数字按照螺旋的顺序进行放置 54. Spiral Matrix start表示的是每次一圈的开始,每次开始其实就是从(0,0).(1,1 ...
-
leetcode 263. Ugly Number 、264. Ugly Number II 、313. Super Ugly Number 、204. Count Primes
263. Ugly Number 注意:1.小于等于0都不属于丑数 2.while循环的判断不是num >= 0, 而是能被2 .3.5整除,即能被整除才去除这些数 class Solution ...
随机推荐
-
Position和anchorPoint
Main.storyboard ViewController.m // // ViewController.m // 7A12.position和anchorPoint // // Create ...
-
OpenTSDB介绍——基于Hbase的分布式的,可伸缩的时间序列数据库,而Hbase本质是列存储
原文链接:http://www.jianshu.com/p/0bafd0168647 OpenTSDB介绍 1.1.OpenTSDB是什么?主要用途是什么? 官方文档这样描述:OpenTSDB is ...
-
浏览器中显示视频,flash等的代码处理
window.flashView=function(flash_url){ var html=''; html+='<div id="obj_flash_div">'; ...
-
A Knight&#39;s Journey
poj2488:http://poj.org/problem?id=2488 题意:给你一张地图,然后有一个骑士,骑士可以从地图的任意一个方格开始,作为起点,问你该骑士能否走遍整张题图.题解:首先想到 ...
-
UILabel的size根据文字的长短变化
UILabel *label = [[UILabel alloc] init]; label.backgroundColor = [UIColor blackColor]; [self.view a ...
-
自动更改IP地址反爬虫*,支持多线程(转)
8年多爬虫经验的人告诉你,国内ADSL是王道,多申请些线路,分布在多个不同的电信机房,能跨省跨市更好,我这里写好的断线重拨组件,你可以直接使用. ADSL拨号上网使用动态IP地址,每一次拨号得到的IP ...
-
C#中函数的功能和类型
函数 就是方法是独立完成某项功能的一个个体 函数的的三个好处:1.提高代码的重用性.2.提高功能开发的效率,3.提高代码的可维护性(主要功能). 函数也分为 固定功能函数(这类函数具有可封闭 ...
-
Python + Anaconda + vscode环境重装(2019.4.20)
目录 卸载程序 安装Ananconda 检查系统环境变量 更换国内镜像源 设置VS CODE 用户配置及工作环境配置 @(Python + Anaconda + vscode环境重装) 工程目录的使用 ...
-
hadoop权威指南学习(一) - 天气预报MapReduce程序的开发和部署
看过Tom White写的Hadoop权威指南(大象书)的朋友一定得从第一个天气预报的Map Reduce程序所吸引, 殊不知,Tom White大牛虽然在书中写了程序和讲解了原理,但是他以为你们都会 ...
-
cygwin下如何运行crontab定时脚本?
1. 安装cron服务(如果不能启动,使用管理员身份运行cygwin) cygrunsrv -I cron -p /usr/sbin/cron -a -D -I 是安装 cron是服务名 -p /us ...