G****A
发帖数: 4160 | 1 给一个string，无空格，无特殊字符，全小写字母。给字典。问总共有多少种可能的断
词方式，so that 每个词都能在字典里查到。
我只想到了dfs. |
w********p
发帖数: 948 | 2 这个和DFS 没关系啊。典型的DP题啊。 CC 150 上有答案。
【在 G****A 的大作中提到】
: 给一个string，无空格，无特殊字符，全小写字母。给字典。问总共有多少种可能的断
: 词方式，so that 每个词都能在字典里查到。
: 我只想到了dfs.
|
x*********w
发帖数: 533 | 3
二爷的标准说法是 dfs+cache
【在 w********p 的大作中提到】
: 这个和DFS 没关系啊。典型的DP题啊。 CC 150 上有答案。
|
b*****n
发帖数: 618 | 4 DFS和DP本质上一样吧，DP存了已经查找过的结果，DFS每次要重新找 |
h*******e
发帖数: 1377 | |
k****e
发帖数: 116 | 6 貌似是DP
【在 G****A 的大作中提到】
: 给一个string，无空格，无特殊字符，全小写字母。给字典。问总共有多少种可能的断
: 词方式，so that 每个词都能在字典里查到。
: 我只想到了dfs.
|
G****A
发帖数: 4160 | 7 手头刚好没有cc150，你说的解法类似这个么？还有没有其他解法？
void sentence(string input, int left, int right, string output, map
bool> dict)
{
if (left > right)
cout<
else{
for (int i=left; i<=right; i++){
std::string sub = input.substr(left, i-left+1);
if (dict.find(sub) != dict.end())
sentence(input, i+1, right, output + sub + " ", dict);
}
}
}
【在 w********p 的大作中提到】
: 这个和DFS 没关系啊。典型的DP题啊。 CC 150 上有答案。
|
n*******w
发帖数: 687 | 8 这个是递归解。至少指数级复杂度。
DP是n^2
【在 G****A 的大作中提到】
: 手头刚好没有cc150，你说的解法类似这个么？还有没有其他解法？
: void sentence(string input, int left, int right, string output, map: bool> dict)
: {
: if (left > right)
: cout<: else{
: for (int i=left; i<=right; i++){
: std::string sub = input.substr(left, i-left+1);
: if (dict.find(sub) != dict.end())
|
w********p
发帖数: 948 | 9 你倒是提醒我了。
首先dict 是给你的没错，但是它是个什么样的字典呢？你要考虑
最佳答案是 Trie. 和DP 结合起来用。
Trie 在分析词汇的时候有三种可能
1） 没有
2） 是的
3） 部分存在。
所以简化你的方法，要快一点。
【在 G****A 的大作中提到】
: 手头刚好没有cc150，你说的解法类似这个么？还有没有其他解法？
: void sentence(string input, int left, int right, string output, map: bool> dict)
: {
: if (left > right)
: cout<: else{
: for (int i=left; i<=right; i++){
: std::string sub = input.substr(left, i-left+1);
: if (dict.find(sub) != dict.end())
|
j******2
发帖数: 362 | 10 150里就是trie+dp
【在 w********p 的大作中提到】
: 你倒是提醒我了。
: 首先dict 是给你的没错，但是它是个什么样的字典呢？你要考虑
: 最佳答案是 Trie. 和DP 结合起来用。
: Trie 在分析词汇的时候有三种可能
: 1） 没有
: 2） 是的
: 3） 部分存在。
: 所以简化你的方法，要快一点。
|
