139. Word Break(动态规划)
2024-08-28 23:16:04
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because"leetcode"
can be segmented as"leet code"
.
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because"
applepenapple"
can be segmented as"
apple pen apple"
.
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
dp[i] 0-i这个字符串是否满足wordbreak
dp[0] = 0
dp[1] =dp[0] && s[0:1] in dict
dp[2] =dp[0] && s[0:1] in dict || dp[1] && s[1:2] in dict
dp[3] =dp[0] && s[0:3] in dict || dp[1] && s[1:3] in dict || dp[2] && s[2:3] in dict
dp[i] =dp[0] && s[0:i] in dict || ,,,,,,,||dp[i-1]&& s[i-1:i] in dict
Time complexity O(n^2)
Space complexity O(n)
语法注意:
s = "abcde"; 要得到”ce“
string word = s.substr(2,2);
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+,false);
unordered_set<string>dict(wordDict.begin(),wordDict.end());
dp[] = true;
for(int i = ; i<=s.size();i++){
for(int j = ;j<i;j++){
string word = s.substr(j,i-j);
if(dp[j]&&dict.find(word)!=dict.end()){
cout<<word<<endl;
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};
参考:
http://zxi.mytechroad.com/blog/leetcode/leetcode-139-word-break/
最新文章
- 基于Quick-cocos2d-x的资源更新方案 一
- Django学习笔记之二
- oracle 关键字
- asp.net 一次性提交大量数据,服务器会报错,要在 web.config 中设置一下
- [IOS NSUserDefaults]的使用:登陆后不再显示登录界面。
- Servlet域对象ServletContext小应用------计算网站访问量
- NGINX怎样处理惊群的
- oracle体系结构详细示意图
- bootstrap3-typeahead 自动补全
- html textarea换行和dom换行
- 树莓PI交叉编译BOOST库(asio网络例子)
- spring boot + quartz 集群
- atlassian-jira部署文档
- Convert Spaces to Tabs
- node多文件处理方法
- 短小而精悍的JsvaScript函数
- Spring Boot + Spring Cloud 实现权限管理系统 后端篇(三):搭建开发环境
- Floyd_Warshall算法
- shell实现增加删除Linux系统用户脚本(密码为随机)
- 在Mac OS X上配置Apache2
热门文章
- Python生成器表达式
- python之if __name__ == &#39;__main__&#39;
- rem设置
- 终于解决“Git Windows客户端保存用户名与密码”的问题(转载)
- python面试题~反射,元类,单例
- 简述 cookies 和 session 的区别
- es中对mapping的理解
- 20181226 PL/SQL批量生产处理语句
- UDP网络通信
- 2017-2018-2 20165236 实验四《Android开发基础》实验报告