| 失效链接处理 |
|
LeetCode题解（java语言实现） PDF 下载
本站整理下载：
相关截图：
主要内容：
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()];
}
}
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
