k*******r
发帖数: 355 | 1 split a string into words in a dictionary
我想到的不管是递归还是dp，最坏情况都要O(2^n).有在最坏情况还能维持多项式时间
的解法么？哪位说一下？ |
w****x
发帖数: 2483 | 2 DP解法:
dpRec[strlen(str)]
dpRec[i]: if true, previous character can split to words
for (int i = 0; i < strLen; i++)
for (int j = i; j >=0 && !dpRec[i]; j--)
dpRec[i] = true if dpRec[j] && isWord(str[j..i])
时间复杂度O(n^2) |
l***i
发帖数: 1309 | 3 One question, can you use the same word in dict more than once?
if yes then wwwyhx gives correct solution. |
k*******r
发帖数: 355 | 4 same word应该可以用多次
对， wwwyhx 的算法可以在O(n^2)判断这个string能不能被合法split
但我有一个问题，如果是要打印出所有合法的split， 我觉得这个合法split本身的个
数就可能是exponential的，那怎么可能用多项式时间打印出来呢 |
w****o
发帖数: 2260 | 5 通常dictionary是用什么数据结构表示的？我想这对解决本题关系很大吧？!
谢谢！
【在 k*******r 的大作中提到】
: split a string into words in a dictionary
: 我想到的不管是递归还是dp，最坏情况都要O(2^n).有在最坏情况还能维持多项式时间
: 的解法么？哪位说一下？
|
g**********y
发帖数: 14569 | 6 内层循环可以优化，字典里最长单词长度是个常数C
所以DP搜索只需要O(N)
但是收集答案可以是exponential, 因为答案空间就是那么大。
【在 w****x 的大作中提到】
: DP解法:
: dpRec[strlen(str)]
: dpRec[i]: if true, previous character can split to words
: for (int i = 0; i < strLen; i++)
: for (int j = i; j >=0 && !dpRec[i]; j--)
: dpRec[i] = true if dpRec[j] && isWord(str[j..i])
: 时间复杂度O(n^2)
|
