split a string into words in a dictionary这题有最坏情况比exponential 快的解法么？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

split a string into words in a dictionary这题有最坏情况比exponential 快的解法么？

split a string into words in a dictionary这题有最坏情况比exponential 快的解法么？# JobHunting - 待字闺中

k*r2012-03-17 07:03

1 楼

split a string into words in a dictionary
我想到的不管是递归还是dp，最坏情况都要O(2^n).有在最坏情况还能维持多项式时间
的解法么？哪位说一下？

w*x2012-03-17 07:03

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*i2012-03-17 07:03

3 楼

One question, can you use the same word in dict more than once?
if yes then wwwyhx gives correct solution.

k*r2012-03-17 07:03

4 楼

same word应该可以用多次
对， wwwyhx 的算法可以在O(n^2)判断这个string能不能被合法split
但我有一个问题，如果是要打印出所有合法的split，我觉得这个合法split本身的个
数就可能是exponential的，那怎么可能用多项式时间打印出来呢

w*o2012-03-17 07:03

5 楼

通常dictionary是用什么数据结构表示的？我想这对解决本题关系很大吧？!
谢谢！

【在 k*******r 的大作中提到】

: split a string into words in a dictionary
: 我想到的不管是递归还是dp，最坏情况都要O(2^n).有在最坏情况还能维持多项式时间
: 的解法么？哪位说一下？

g*y2012-03-17 07:03

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)