leetcode的新题是1337c0d3r本人在更新吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode的新题是1337c0d3r本人在更新吗？

leetcode的新题是1337c0d3r本人在更新吗？# JobHunting - 待字闺中

l*n2013-10-05 07:10

1 楼

这就来了个流行的word break的题目，真是与时俱进啊。

z*82013-10-05 07:10

2 楼

我贡献的血汗题目啊。。。

【在 l*n 的大作中提到】

: 这就来了个流行的word break的题目，真是与时俱进啊。

y*n2013-10-05 07:10

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*o2013-10-05 07:10

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*n2013-10-05 07:10

5 楼

Nice.

T*e2013-10-05 07:10

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*m2013-10-05 07:10

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;iif(!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*82013-10-05 07:10

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;
}
}