Re: 李10年进去后会不会被爆菊？# Joke - 肚皮舞运动
a*e
1 楼
请教leetcode上的那道Word Break II
Given a string s and a dictionary of words dict, add spaces in s to
construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
http://oj.leetcode.com/problems/word-break-ii/
Can anyone tell me why the following code generated Memory Limit Exceeded? I
tested it in VS for that catsanddog string, which works.
class Solution { public: vector wordBreak(string s, unordered_set &dict) {
int len = s.length();
bool *can =new bool[len+1];
can[0] = true;
for (int i=1;i
vector> dp(len+1, vector());
dp[0].push_back("");
string str;
for (int i=1; i<=len; i++)
for (int j=0;j{
str = s.substr(j,i-j);
if (can[j]&&dict.find(str)!=dict.end())
{
can[i]=true;
string empty;
if (j>0) empty = " ";
for (int idx=0; idx
string n = dp[j][idx] + empty + str;
dp[i].push_back(n);
}
}
}
return dp[len];
}
};
Given a string s and a dictionary of words dict, add spaces in s to
construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
http://oj.leetcode.com/problems/word-break-ii/
Can anyone tell me why the following code generated Memory Limit Exceeded? I
tested it in VS for that catsanddog string, which works.
class Solution { public: vector wordBreak(string s, unordered_set &dict) {
int len = s.length();
bool *can =new bool[len+1];
can[0] = true;
for (int i=1;i
vector
dp[0].push_back("");
string str;
for (int i=1; i<=len; i++)
for (int j=0;j{
str = s.substr(j,i-j);
if (can[j]&&dict.find(str)!=dict.end())
{
can[i]=true;
string empty;
if (j>0) empty = " ";
for (int idx=0; idx
string n = dp[j][idx] + empty + str;
dp[i].push_back(n);
}
}
}
return dp[len];
}
};
