l*n
发帖数: 529 | 1 这就来了个流行的word break的题目，真是与时俱进啊。 |
z*********8
发帖数: 2070 | 2 我贡献的血汗题目啊。。。
【在 l*n 的大作中提到】
: 这就来了个流行的word break的题目，真是与时俱进啊。
|
y***n
发帖数: 1594 | 3 Is this a DP problem, I tried a recursive solution which exceeds time limit
bool wordBreak(string s, unordered_set &dict) {
if(s.length()==0) return true;
bool foundBreak=false;
for(const string& current: dict){
if(s.compare(0, current.size(),current)==0){//find current
foundBreak= wordBreak(s.substr(current.size()), dict);
if(foundBreak)
break;
}
}
return foundBreak;
} |
l****o
发帖数: 315 | 4 public class Solution {
public boolean wordBreak(String s, Set dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for (int i = 0; i <= s.length(); i++)
for (int j = 0; j < i; j++)
if (f[j] && dict.contains(s.substring(j, i))) {
f[i] = true;
break;
}
return f[s.length()];
}
} |
y***n
发帖数: 1594 | |
T*******e
发帖数: 4928 | 6 哈，咱们思路差不多。
bool wordBreak(string s, unordered_set &dict) { //Time: O(n^2)
int sSize=s.size();
if(sSize<=0||dict.empty()) return false;
vector isWord(sSize+1, false);
isWord[0]=true;
for(int i=1; i<=sSize; ++i) {
for(int j=i-1; j>=0; --j) {
if(dict.find(s.substr(j, i-j))!=dict.end() &&isWord[j]) {
isWord[i]=true;
break;
}
}
}
return isWord[sSize];
}
reused
【在 l****o 的大作中提到】
: public class Solution {
: public boolean wordBreak(String s, Set dict) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: boolean[] f = new boolean[s.length() + 1];
: f[0] = true;
: for (int i = 0; i <= s.length(); i++)
: for (int j = 0; j < i; j++)
: if (f[j] && dict.contains(s.substring(j, i))) {
: f[i] = true;
|
b**m
发帖数: 1466 | 7 其实是前几天有人问那个(10)的简化版：
public class Solution {
public boolean wordBreak(String s, Set dict) {
if(s.length()==0){
return dict.contains(s);
}
boolean[] reachable = new boolean[s.length()+1];
reachable[0] = true;
for(int i=0;i
if(!reachable[i]){
continue;
}
for(int j=i+1;j<=s.length();j++){
String e = s.substring(i,j);
if(dict.contains(e)){
reachable[j] = true;
}
}
}
return reachable[reachable.length-1];
}
} |
z*********8
发帖数: 2070 | 8 这个case老是fail在这个test case：
Submission Result: Runtime Error
Last executed input: "aaaaaaa", ["aaaa","aa"]
谁能帮我看看？
public class Solution {
public boolean wordBreak(String s, Set dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
boolean[] result = new boolean[s.length()+1];
result[0] = true;
int size = s.length();
for(int i=1; i <= size; ++i)
{
if(result[i] == false && dict.contains(s.substring(0,i)))
{
result[i] = true;
}
if(result[i])
{
if(i==size)
{
return true;
}
for(int j= i+1; j <= size; ++j)
{
if(result[j] == false && dict.contains(s.substring(i,j-i
)))
{
result[j] = true;
}
if(result[j] && j== size)
{
return true;
}
}
}
}
return false;
}
} |
