Java知识分享网 - 轻松学习从此开始!    

Java知识分享网

Java1234官方群25:java1234官方群17
Java1234官方群25:838462530
        

最新Java全栈就业实战课程(免费)

springcloud分布式电商秒杀实战课程

IDEA永久激活

66套java实战课程无套路领取

Java1234 VIP课程

Java毕业设计指导(联系锋哥)

Java毕业设计指导(联系锋哥)         Java1234至尊VIP(特价活动)

LeetCode题解(java语言实现) PDF 下载


分享到:
时间:2021-12-13 10:01来源:http://www.java1234.com 作者:转载  侵权举报
LeetCode题解(java语言实现) PDF 下载
失效链接处理
LeetCode题解(java语言实现) PDF 下载


本站整理下载:
提取码:dvg3 
 
 
相关截图:
 
主要内容:

 Solution Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into
a space-separated sequence of one or more dictionary words. For example, given s =
"leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as
"leet code".
15 | 181
4 Solution Word Break
4.1 Naive Approach
This problem can be solve by using a naive approach, which is trivial. A discussion
can always start from that though.
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
return wordBreakHelper(s, dict, 0);
}
public boolean wordBreakHelper(String s, Set<String> dict, int start){
if(start == s.length())
return true;
for(String a: dict){
int len = a.length();
int end = start+len;
//end index should be <= string length
if(end > s.length())
continue;
if(s.substring(start, start+len).equals(a))
if(wordBreakHelper(s, dict, start+len))
return true;
}
return false;
}
}
Time: O(nˆ 2)
This solution exceeds the time limit.
4.2 Dynamic Programming
The key to solve this problem by using dynamic programming approach:
• Define an array t[] such that t[i]==true =>0-(i-1) can be segmented using dictio-
nary
• Initial state t[0] == true
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] t = new boolean[s.length()+1];
t[0] = true; //set first to be true, why?
//Because we need initial state
for(int i=0; i<s.length(); i++){
16 | 181 Program Creek
4 Solution Word Break
//should continue from match position
if(!t[i])
continue;
for(String a: dict){
int len = a.length();
int end = i + len;
if(end > s.length())
continue;
if(t[end]) continue;
if(s.substring(i, end).equals(a)){
t[end] = true;
}
}
}
return t[s.length()];
}
}
 

------分隔线----------------------------

锋哥公众号


锋哥微信


关注公众号
【Java资料站】
回复 666
获取 
66套java
从菜鸡到大神
项目实战课程

锋哥推荐