logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
精巧的门铃按纽
avatar
精巧的门铃按纽# Joke - 肚皮舞运动
b*y
1 楼
求教各位大拿，这道面试题怎么解
Find Longest Word Made of Other Words： Write a program that reads a file
containing a sorted list of words (one word per line, no spaces, all lower
case), then identifies the longest word in the file that can be constructed
by concatenating copies of shorter words also found in the file.
给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了
avatar
w*n
2 楼
5.5-cup的职能煮米饭
煮稀饭想买10-cup的
普通的rice cooker煮稀饭喷的到处都是
avatar
y*o
3 楼
大家都知道，当版主是苦差事，负责管理，负责删帖，负责随时被人乱砸。作版主要投
入很多精力和苦力，我们在这里玩得不亦乐乎有版主的一份功劳，我代表各大水车们谢
谢版主！
avatar
r*e
4 楼
精巧的门铃按纽.jpg
avatar
p*2
5 楼
DP呀。
avatar
p*t
6 楼
我买的高压锅，煮饭，煮粥，炖肉，熬汤什么都解决了
觉得特值当
avatar
b*k
7 楼
没错。请我当我都不当

【在 y*****o 的大作中提到】
: 大家都知道，当版主是苦差事，负责管理，负责删帖，负责随时被人乱砸。作版主要投
: 入很多精力和苦力，我们在这里玩得不亦乐乎有版主的一份功劳，我代表各大水车们谢
: 谢版主！
avatar
z*c
8 楼
我的想法：
假设一个短的单词可以被用多次来组成一个长单词，比如['a', 'aaaa']，如果只用一
次就不会了
如果这样的话，从长到短枚举单词，设W，用动态规划判断W是否是复合单词。
F[i]表示W的前i个字符是否能被分解，true可以，false不行
F[i] = true, 如果存在k，使得F[i - k] = true，并且W[i - k + 1, i]这段字符串在
字典里存在
状态数O(L)
决策数O(L)
判断是否存在字典可以用Trie, O(L)
动态规划复杂度O(L^3)，总复杂度O(NL^3)
可以优化一个地方，就是决策当决策从小到大增加的时候，要不断去Trie检查
W[i, i]
W[i - 1, i]
W[i - 2, i]
...
W[i - k + 1, i]
是不是存在，我们可以把所有单词按照反序插入，比如abcd，那么插入普通Trie的时候
是a是根，那么反序就是d是根，那么当决策k增加的时候，就可以直接在Trie中一边行
走一边判断了，动态规划的总的复杂度可以减少一个L的判断时间，变成O(L^2)，总的
优化成O(NL^2)
CareerCup上好像有个solution，不过我没仔细看。
avatar
w*n
9 楼
不敢用...我有普通高压锅...家里没人敢用

【在 p******t 的大作中提到】
: 我买的高压锅，煮饭，煮粥，炖肉，熬汤什么都解决了
: 觉得特值当
avatar
f*h
10 楼
最怕听“没有辛劳也有苦劳”这种话。还是支持“没有金刚钻，别揽瓷器活”。
avatar
b*y
11 楼
请问什么是DP?

【在 p*****2 的大作中提到】
: DP呀。
avatar
p*t
12 楼
...
我这个是电的，压根没什么动静，现在天天煮饭都用它
觉得比普通rice cooker好用无数倍，节能是一方面，还有不会喷蒸汽很重要
我原来的rice cooker把天花板都喷脏了一圈，很讨厌
普通的高压锅，我不会用也不敢用

【在 w***n 的大作中提到】
: 不敢用...我有普通高压锅...家里没人敢用
avatar
y*o
13 楼
刚才竟然有人发短信骂我，呵呵呵，我们水车只是谢谢版主的劳动，和版主是谁没关系
，骂我的人，我敢说如果你当版主付出辛勤劳动，我也会谢谢你。
avatar
p*2
14 楼

dynamic programming

【在 b**y 的大作中提到】
: 请问什么是DP?
avatar
w*r
15 楼
赞rice cooker

【在 p******t 的大作中提到】
: ...
: 我这个是电的，压根没什么动静，现在天天煮饭都用它
: 觉得比普通rice cooker好用无数倍，节能是一方面，还有不会喷蒸汽很重要
: 我原来的rice cooker把天花板都喷脏了一圈，很讨厌
: 普通的高压锅，我不会用也不敢用
avatar
c*n
16 楼
以前不是说么，没被短信问候过的都不是名ID
恭喜你成为名ID了。

【在 y*****o 的大作中提到】
: 刚才竟然有人发短信骂我，呵呵呵，我们水车只是谢谢版主的劳动，和版主是谁没关系
: ，骂我的人，我敢说如果你当版主付出辛勤劳动，我也会谢谢你。
avatar
b*y
17 楼
谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
两个单词组成
以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
用过Trie）
对每个单词用动态规划判断W是否是复合单词
for every position i(except n) in word W
if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
return true;
return false
记录下最长的复合单词,可行吗？

【在 z********c 的大作中提到】
: 我的想法：
: 假设一个短的单词可以被用多次来组成一个长单词，比如['a', 'aaaa']，如果只用一
: 次就不会了
: 如果这样的话，从长到短枚举单词，设W，用动态规划判断W是否是复合单词。
: F[i]表示W的前i个字符是否能被分解，true可以，false不行
: F[i] = true, 如果存在k，使得F[i - k] = true，并且W[i - k + 1, i]这段字符串在
: 字典里存在
: 状态数O(L)
: 决策数O(L)
: 判断是否存在字典可以用Trie, O(L)
avatar
l*o
18 楼
弄个慢炖锅好了

【在 w***n 的大作中提到】
: 5.5-cup的职能煮米饭
: 煮稀饭想买10-cup的
: 普通的rice cooker煮稀饭喷的到处都是
avatar
s*g
19 楼
that's laodaye, the godmother of all trolls

【在 y*****o 的大作中提到】
: 刚才竟然有人发短信骂我，呵呵呵，我们水车只是谢谢版主的劳动，和版主是谁没关系
: ，骂我的人，我敢说如果你当版主付出辛勤劳动，我也会谢谢你。
avatar
p*2
20 楼

我觉得这题trie不是考点。dictionary用hashtable就可以了。考点应该是DP

【在 b**y 的大作中提到】
: 谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
: 两个单词组成
: 以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
: 所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
: opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
: 用过Trie）
: 对每个单词用动态规划判断W是否是复合单词
: for every position i(except n) in word W
: if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
: return true;
avatar
m*g
21 楼
laodaye的马甲。它和所有版主和前版主有仇，所以凡是说版主好话的人都自动变成它
的仇人了。

【在 y*****o 的大作中提到】
: 刚才竟然有人发短信骂我，呵呵呵，我们水车只是谢谢版主的劳动，和版主是谁没关系
: ，骂我的人，我敢说如果你当版主付出辛勤劳动，我也会谢谢你。
avatar
b*y
22 楼
谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
知道hashtable和trie哪个容易实现排序？

【在 p*****2 的大作中提到】
:
: 我觉得这题trie不是考点。dictionary用hashtable就可以了。考点应该是DP
avatar
K*n
23 楼
多谢理解和支持! :-)

【在 y*****o 的大作中提到】
: 大家都知道，当版主是苦差事，负责管理，负责删帖，负责随时被人乱砸。作版主要投
: 入很多精力和苦力，我们在这里玩得不亦乐乎有版主的一份功劳，我代表各大水车们谢
: 谢版主！
avatar
p*2
24 楼

如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
以了。

【在 b**y 的大作中提到】
: 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
: 还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
: 知道hashtable和trie哪个容易实现排序？
avatar
T*T
25 楼
Don't take it too personally...ain't nothing but hot air..
Enjoy Sat's Meet..

【在 K****n 的大作中提到】
: 多谢理解和支持! :-)
avatar
z*4
26 楼
trie也不是最优的，最优的是dag

另外
，不

【在 p*****2 的大作中提到】
:
: 如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
: 是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
: 以了。
avatar
b*y
27 楼
谢谢楼上zhangchitc，peking 和zyf674 的热心回复，大概的思路有了，不过要补的课很多，剪枝和dag都没用过
avatar
d*u
28 楼
DAG-directed acyclic graph??
Why is it optimal? Even better than Hashmap in terms of time?

【在 z****4 的大作中提到】
: trie也不是最优的，最优的是dag
:
: 另外
: ，不
avatar
z*4
29 楼
存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧

【在 d******u 的大作中提到】
: DAG-directed acyclic graph??
: Why is it optimal? Even better than Hashmap in terms of time?
avatar
d*u
30 楼
如果collision多的话,hashmap确实很难O(1)
能说一下DAG好在哪里吗？

【在 z****4 的大作中提到】
: 存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧
avatar
z*4
31 楼
dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
全一样的。

【在 d******u 的大作中提到】
: 如果collision多的话,hashmap确实很难O(1)
: 能说一下DAG好在哪里吗？
avatar
d*u
32 楼
I see. Thank you !

【在 z****4 的大作中提到】
: dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
: 话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
: 全一样的。
avatar
b*y
33 楼
实现代码:
// build hashtable hset
//遍历hset, 判断每个单词是不是复合词
string FindLongestCompositeWord ()
{
uint32 max_word_length = 1; //No composite word length of 1
string longestCompWord ;
hash_set ::iterator hs1_pIter;
for ( hs1_pIter = hset.begin( ); hs1_pIter != hset.end( ); hs1_pIter++ )
{
if (IsCompositeWord(*hs1_pIter))
{
output_word_list.push_back(*hs1_pIter);
if (max_word_length < ((string)*hs1_pIter).length() )
{
max_word_length = ((string)*hs1_pIter).length() ;
longestCompWord = *hs1_pIter;
}
}
}
return longestCompWord;
}
bool IsCompositeWord(string word)
{
uint32 n = word.length();
//for one character string
if (n==1)
return (hset.find(word)!= hset.end());

//For string length of 2 or more, check if string is made of two or more
words, return true
for (uint32 i =1; i <=n-1; i++)
{
if(hset.find(word.substr (0, i)) != hset.end() &&
(hset.find(word.substr(i,n-i)) != hset.end() || IsCompositeWord(word.
substr(i,n-i))))
return true;
}
return false;
}
avatar
i*e
34 楼
楼上说了，DP 是最优的。
上次实现的是最容易想到的 backtrack + trie 来剪枝优化。虽然测试了一个字典，不
到一秒就出结果，theoretical worst case复杂度还是exponential 的。
这里给你做参考:
http://www.mitbbs.com/article_t/JobHunting/31926643.html
avatar
b*y
35 楼
求教各位大拿，这道面试题怎么解
Find Longest Word Made of Other Words： Write a program that reads a file
containing a sorted list of words (one word per line, no spaces, all lower
case), then identifies the longest word in the file that can be constructed
by concatenating copies of shorter words also found in the file.
给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了
avatar
p*2
36 楼
DP呀。
avatar
z*c
37 楼
我的想法：
假设一个短的单词可以被用多次来组成一个长单词，比如['a', 'aaaa']，如果只用一
次就不会了
如果这样的话，从长到短枚举单词，设W，用动态规划判断W是否是复合单词。
F[i]表示W的前i个字符是否能被分解，true可以，false不行
F[i] = true, 如果存在k，使得F[i - k] = true，并且W[i - k + 1, i]这段字符串在
字典里存在
状态数O(L)
决策数O(L)
判断是否存在字典可以用Trie, O(L)
动态规划复杂度O(L^3)，总复杂度O(NL^3)
可以优化一个地方，就是决策当决策从小到大增加的时候，要不断去Trie检查
W[i, i]
W[i - 1, i]
W[i - 2, i]
...
W[i - k + 1, i]
是不是存在，我们可以把所有单词按照反序插入，比如abcd，那么插入普通Trie的时候
是a是根，那么反序就是d是根，那么当决策k增加的时候，就可以直接在Trie中一边行
走一边判断了，动态规划的总的复杂度可以减少一个L的判断时间，变成O(L^2)，总的
优化成O(NL^2)
CareerCup上好像有个solution，不过我没仔细看。
avatar
b*y
38 楼
请问什么是DP?

【在 p*****2 的大作中提到】
: DP呀。
avatar
p*2
39 楼

dynamic programming

【在 b**y 的大作中提到】
: 请问什么是DP?
avatar
b*y
40 楼
谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
两个单词组成
以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
用过Trie）
对每个单词用动态规划判断W是否是复合单词
for every position i(except n) in word W
if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
return true;
return false
记录下最长的复合单词,可行吗？

【在 z********c 的大作中提到】
: 我的想法：
: 假设一个短的单词可以被用多次来组成一个长单词，比如['a', 'aaaa']，如果只用一
: 次就不会了
: 如果这样的话，从长到短枚举单词，设W，用动态规划判断W是否是复合单词。
: F[i]表示W的前i个字符是否能被分解，true可以，false不行
: F[i] = true, 如果存在k，使得F[i - k] = true，并且W[i - k + 1, i]这段字符串在
: 字典里存在
: 状态数O(L)
: 决策数O(L)
: 判断是否存在字典可以用Trie, O(L)
avatar
p*2
41 楼

我觉得这题trie不是考点。dictionary用hashtable就可以了。考点应该是DP

【在 b**y 的大作中提到】
: 谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
: 两个单词组成
: 以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
: 所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
: opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
: 用过Trie）
: 对每个单词用动态规划判断W是否是复合单词
: for every position i(except n) in word W
: if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
: return true;
avatar
b*y
42 楼
谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
知道hashtable和trie哪个容易实现排序？

【在 p*****2 的大作中提到】
:
: 我觉得这题trie不是考点。dictionary用hashtable就可以了。考点应该是DP
avatar
p*2
43 楼

如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
以了。

【在 b**y 的大作中提到】
: 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
: 还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
: 知道hashtable和trie哪个容易实现排序？
avatar
z*4
44 楼
trie也不是最优的，最优的是dag

另外
，不

【在 p*****2 的大作中提到】
:
: 如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
: 是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
: 以了。
avatar
b*y
45 楼
谢谢楼上zhangchitc，peking 和zyf674 的热心回复，大概的思路有了，不过要补的课很多，剪枝和dag都没用过
avatar
d*u
46 楼
DAG-directed acyclic graph??
Why is it optimal? Even better than Hashmap in terms of time?

【在 z****4 的大作中提到】
: trie也不是最优的，最优的是dag
:
: 另外
: ，不
avatar
z*4
47 楼
存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧

【在 d******u 的大作中提到】
: DAG-directed acyclic graph??
: Why is it optimal? Even better than Hashmap in terms of time?
avatar
d*u
48 楼
如果collision多的话,hashmap确实很难O(1)
能说一下DAG好在哪里吗？

【在 z****4 的大作中提到】
: 存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧
avatar
z*4
49 楼
dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
全一样的。

【在 d******u 的大作中提到】
: 如果collision多的话,hashmap确实很难O(1)
: 能说一下DAG好在哪里吗？
avatar
d*u
50 楼
I see. Thank you !

【在 z****4 的大作中提到】
: dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
: 话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
: 全一样的。
avatar
b*y
51 楼
实现代码:
// build hashtable hset
//遍历hset, 判断每个单词是不是复合词
string FindLongestCompositeWord ()
{
uint32 max_word_length = 1; //No composite word length of 1
string longestCompWord ;
hash_set ::iterator hs1_pIter;
for ( hs1_pIter = hset.begin( ); hs1_pIter != hset.end( ); hs1_pIter++ )
{
if (IsCompositeWord(*hs1_pIter))
{
output_word_list.push_back(*hs1_pIter);
if (max_word_length < ((string)*hs1_pIter).length() )
{
max_word_length = ((string)*hs1_pIter).length() ;
longestCompWord = *hs1_pIter;
}
}
}
return longestCompWord;
}
bool IsCompositeWord(string word)
{
uint32 n = word.length();
//for one character string
if (n==1)
return (hset.find(word)!= hset.end());

//For string length of 2 or more, check if string is made of two or more
words, return true
for (uint32 i =1; i <=n-1; i++)
{
if(hset.find(word.substr (0, i)) != hset.end() &&
(hset.find(word.substr(i,n-i)) != hset.end() || IsCompositeWord(word.
substr(i,n-i))))
return true;
}
return false;
}
avatar
i*e
52 楼
楼上说了，DP 是最优的。
上次实现的是最容易想到的 backtrack + trie 来剪枝优化。虽然测试了一个字典，不
到一秒就出结果，theoretical worst case复杂度还是exponential 的。
这里给你做参考:
http://www.mitbbs.com/article_t/JobHunting/31926643.html
avatar
t*e
53 楼
如果把
(hset.find(word.substr(i,n-i)) != hset.end() || IsCompositeWord(word.
substr(i,n-i))))
改为：
(hset.find(word.substr(i)) != hset.end() || IsCompositeWord(word.
substr(i))))
有什么区别？
avatar
t*e
54 楼
如果把
(hset.find(word.substr(i,n-i)) != hset.end() || IsCompositeWord(word.
substr(i,n-i))))
改为：
(hset.find(word.substr(i)) != hset.end() || IsCompositeWord(word.
substr(i))))
有什么区别？
avatar
c*a
55 楼
这题是cc150里面的啊
avatar
t*e
56 楼
如果把
(hset.find(word.substr(i,n-i)) != hset.end() || IsCompositeWord(word.
substr(i,n-i))))
改为：
(hset.find(word.substr(i)) != hset.end() || IsCompositeWord(word.
substr(i))))
有什么区别？
avatar
t*e
57 楼
如果把
(hset.find(word.substr(i,n-i)) != hset.end() || IsCompositeWord(word.
substr(i,n-i))))
改为：
(hset.find(word.substr(i)) != hset.end() || IsCompositeWord(word.
substr(i))))
有什么区别？
avatar
c*a
58 楼
这题是cc150里面的啊
avatar
m*s
59 楼
请问可否先按词的长度排序，然后在构建Trie时一边加节点一边判断当时的词是否由前
面已加的词组成？
写算法时发现结构很复杂，很多状态要考虑，不知这么思考有无根本上的问题？
请大家见谅把这么老的题拿出来鞭尸。。。
avatar
r*n
60 楼
我觉得上面各位的解法都忽略了一个重要的条件：sorted
显然如果一个词可以分解成其他词的组合，那么这个词一定和其第一个分词靠得很近，
比如
aa
aabbccaa
bb
bbc
bbbbbb
cc
ccbb
aabbccaa的第一个分词是aa，在这个例子中aabbccaa和aa相邻
这道题可以用binary search来解，需要用binary search实现一个equal_range的函数
，然后在search分词的同时，需要用到most-significant-digit string sort的idea。
复杂度 O(MNlogN)，M is the average word length and N is the number of words

constructed

【在 b**y 的大作中提到】
: 求教各位大拿，这道面试题怎么解
: Find Longest Word Made of Other Words： Write a program that reads a file
: containing a sorted list of words (one word per line, no spaces, all lower
: case), then identifies the longest word in the file that can be constructed
: by concatenating copies of shorter words also found in the file.
: 给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了
avatar
h*0
61 楼
没看懂。。 详细点被

【在 r*********n 的大作中提到】
: 我觉得上面各位的解法都忽略了一个重要的条件：sorted
: 显然如果一个词可以分解成其他词的组合，那么这个词一定和其第一个分词靠得很近，
: 比如
: aa
: aabbccaa
: bb
: bbc
: bbbbbb
: cc
: ccbb
avatar
h*0
62 楼
二爷，dp咋做啊？ 求不吝赐教

【在 p*****2 的大作中提到】
:
: 如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
: 是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
: 以了。
avatar
r*n
63 楼
0：aa
1：aabbccaa
2：bb
3：bbc
4：bbbbbb
5：cc
6：ccbb
比如你要判断A = aabbccaa能否由其他词组成：
A[0] = a，所以你在所有words里面做binary search（with respect to the first
char），你发现arr[0]，和arr[1]是由char a开头的
然后在[0,1]里面binary search A[1] = a（with respect to 2nd char），你还是得
到[0, 1]，这个时候因为arr[0]只有2个char，所以你发现arr[0]是A的prefix。
然后在[0 - 6]里面binary search A[2] = b（with respect to 1st char），你得到[
2,3,4]
然后在[2，3，4]里面binary search A[3] = b（with respect to 1st char），你得
到[2,3,4]....
整个思路和MSD string sort是一样的，解释起来比较verbose，你理解了MSD sort，也
就理解这个算法了。

【在 h*******0 的大作中提到】
: 没看懂。。 详细点被
avatar
m*s
64 楼
但这样会得到A = aa bbc 然后会得到不是组合的结果。而实际上A = aa bb cc bb...
觉得难点在bb之后，如何决定c从头开始还是在bb之后？

【在 r*********n 的大作中提到】
: 0：aa
: 1：aabbccaa
: 2：bb
: 3：bbc
: 4：bbbbbb
: 5：cc
: 6：ccbb
: 比如你要判断A = aabbccaa能否由其他词组成：
: A[0] = a，所以你在所有words里面做binary search（with respect to the first
: char），你发现arr[0]，和arr[1]是由char a开头的
avatar
r*n
65 楼
在确定aa bb 之后一条路是restart，另外一条路是一直下去，所以也有dfs的意思在里
面，并不是greedy algorithm，找最长match。

【在 m******s 的大作中提到】
: 但这样会得到A = aa bbc 然后会得到不是组合的结果。而实际上A = aa bb cc bb...
: 觉得难点在bb之后，如何决定c从头开始还是在bb之后？
avatar
m*s
66 楼
同求DP解法：
对于有M个字的词，我可以想到的需要M^2额外空间记录：
在第k+1步，新字符c[k], 已有表格纪录c[i,j]是否是组合词，然后对c[0..l]如果是组
合词，检查c[l+1..k]是否是组合词，只需检验c[k-1,k],c[k-2,k]...是否在辞典里。
但最慢的可能是O(M*M)

【在 i**********e 的大作中提到】
: 楼上说了，DP 是最优的。
: 上次实现的是最容易想到的 backtrack + trie 来剪枝优化。虽然测试了一个字典，不
: 到一秒就出结果，theoretical worst case复杂度还是exponential 的。
: 这里给你做参考:
: http://www.mitbbs.com/article_t/JobHunting/31926643.html
avatar
m*s
67 楼
原题解法似乎不能涵盖所有情况：
aa aabbcc bb bbc cc
把aabbcc拆分成两部分：
(a abbcc) (aa bbcc) (aab bcc) (aabb cc) (aabbc c)
其中没有那一对中的两个都被包含在词典里，但aabbcc可以被分成aa bb cc

【在 c*****a 的大作中提到】
: 这题是cc150里面的啊
avatar
s*r
68 楼
为啥我记得是150题里的？
貌似我1小时前刚看。。。
avatar
m*s
69 楼
原题解法CC150
1. Sort the array by size, putting the longest word at the front
2. For each word, split it in all possible ways. That is, for “test”,
split it into {“t”, “est”}, {“te”, “st”} and {“tes”, “t”}.
3. Then, for each pairing, check if the first half and the second both exist
elsewhere in the array.
4. “Short circuit” by returning the first string we find that fits
condition #3.
原题解法似乎不能涵盖所有情况：
aa aabbcc bb bbc cc
1. Sort: (aabbcc, bbc, aa, bb, cc)
2. 把aabbcc拆分成两部分, 下面是所有的情况：
(a abbcc) (aa bbcc) (aab bcc) (aabb cc) (aabbc c)
3. 不满足，其中没有那一对中的两个都被包含在词典里，但aabbcc可以被分成（aa bb
cc）
请教我哪里想错了吗？

【在 s**********r 的大作中提到】
: 为啥我记得是150题里的？
: 貌似我1小时前刚看。。。
avatar
s*r
70 楼
我只看了题目没看解答，后来找不到题了。。。。
先mark了，等看题的时候来看看你的解法。

exist

【在 m******s 的大作中提到】
: 原题解法CC150
: 1. Sort the array by size, putting the longest word at the front
: 2. For each word, split it in all possible ways. That is, for “test”,
: split it into {“t”, “est”}, {“te”, “st”} and {“tes”, “t”}.
: 3. Then, for each pairing, check if the first half and the second both exist
: elsewhere in the array.
: 4. “Short circuit” by returning the first string we find that fits
: condition #3.
: 原题解法似乎不能涵盖所有情况：
: aa aabbcc bb bbc cc
avatar
m*s
71 楼
前一个想法需要记录很多无用的中间信息，下面的想法除了hash table, 还需记录额外
的m个boolean：IsCombination(c[m-1, m-1]), IsCombination(c[m-2, m-1])...
IsCombination(c[k, m-1])原因是避免重复计算， 试想如果已经递归过IsCombination
(c[k, ... m-1], 那么相应的一些较短的以c[m-1]结尾的字符串也被判断过。
和zhangchitc 想法的区别在于对已遍历的前k个字符不做IsCombination的考虑
代码与之前一个帖子类似但加了中间结果存储：
bool IsCompositeWord(char* word， int start, int end, bool* table)
{
//check whether it is recorded before
if (table[start] == false)
return false;

//check all possible pair: check first is word or not and check is second
combination or not
for (int i = start; i <= end; i++)
{
if((IsWord(str, start, i) == TRUE) && (IsCompositeWord(str, i+1, end,
table) == TRUE))
return true;
}
table[start] = false;
return false;
}
相关阅读
每年有半年在中国，半年在美国。一半时间工作，一半实践休息 (转载)黑， Verizon的Router $150一个恐袭嫌犯落脚酒店和公寓曝光 疑行凶前吸食毒品巴黎恐袭嫌犯母亲：儿子没想杀人 只是压力大深夜福利之苏联女兵蒸桑拿 (转载)Ben Carson: 恶补外交知识，但收效甚微问个不好笑的问题老邢这用的什么数据结构海昏侯陵里挖出来的金银财宝XX不哭是哪个二B发明的啊想找个国女结婚.车的宣传广告词Family Guy讨论国内的二胎政策北京房价三年内，四环20万，五环15万，六环6万 (转载)日本女遊客公车内撒尿，台湾人感到自责 (转载)欲行男女之事时，妹子开口说：哥，真不行啊Angelina Jolie: how to survive terrorist attack法国部长欲在全国所有火车站加装金属探测门 (转载)关闭清真寺Re: 蒋宋美龄的“项链”成了谁的鸡汤 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。