b**y
发帖数: 13 | 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.
给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了 |
p*****2
发帖数: 21240 | |
z********c
发帖数: 72 | 3 我的想法：
假设一个短的单词可以被用多次来组成一个长单词，比如['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，不过我没仔细看。 |
b**y
发帖数: 13 | 4 请问什么是DP?
【在 p*****2 的大作中提到】
: DP呀。
|
p*****2
发帖数: 21240 | 5
dynamic programming
【在 b**y 的大作中提到】
: 请问什么是DP?
|
b**y
发帖数: 13 | 6 谢谢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)
|
p*****2
发帖数: 21240 | 7
我觉得这题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;
|
b**y
发帖数: 13 | 8 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
知道hashtable和trie哪个容易实现排序？
【在 p*****2 的大作中提到】
:
: 我觉得这题trie不是考点。dictionary用hashtable就可以了。考点应该是DP
|
p*****2
发帖数: 21240 | 9
如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
以了。
【在 b**y 的大作中提到】
: 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
: 还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
: 知道hashtable和trie哪个容易实现排序？
|
z****4
发帖数: 194 | 10 trie也不是最优的，最优的是dag
另外
，不
【在 p*****2 的大作中提到】
:
: 如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
: 是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
: 以了。
|
|
|
b**y
发帖数: 13 | 11 谢谢楼上zhangchitc，peking 和zyf674 的热心回复，大概的思路有了，不过要补的课很多，剪枝和dag都没用过 |
d******u
发帖数: 397 | 12 DAG-directed acyclic graph??
Why is it optimal? Even better than Hashmap in terms of time?
【在 z****4 的大作中提到】
: trie也不是最优的，最优的是dag
:
: 另外
: ，不
|
z****4
发帖数: 194 | 13 存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧
【在 d******u 的大作中提到】
: DAG-directed acyclic graph??
: Why is it optimal? Even better than Hashmap in terms of time?
|
d******u
发帖数: 397 | 14 如果collision多的话,hashmap确实很难O(1)
能说一下DAG好在哪里吗？
【在 z****4 的大作中提到】
: 存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧
|
z****4
发帖数: 194 | 15 dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
全一样的。
【在 d******u 的大作中提到】
: 如果collision多的话,hashmap确实很难O(1)
: 能说一下DAG好在哪里吗？
|
d******u
发帖数: 397 | 16 I see. Thank you !
【在 z****4 的大作中提到】
: dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
: 话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
: 全一样的。
|
b**y
发帖数: 13 | 17 实现代码:
// 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;
} |
i**********e
发帖数: 1145 | 18 楼上说了，DP 是最优的。
上次实现的是最容易想到的 backtrack + trie 来剪枝优化。虽然测试了一个字典，不
到一秒就出结果，theoretical worst case复杂度还是exponential 的。
这里给你做参考:
http://www.mitbbs.com/article_t/JobHunting/31926643.html |
b**y
发帖数: 13 | 19 求教各位大拿，这道面试题怎么解
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.
给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了 |
p*****2
发帖数: 21240 | |
|
|
z********c
发帖数: 72 | 21 我的想法：
假设一个短的单词可以被用多次来组成一个长单词，比如['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，不过我没仔细看。 |
b**y
发帖数: 13 | 22 请问什么是DP?
【在 p*****2 的大作中提到】
: DP呀。
|
p*****2
发帖数: 21240 | 23
dynamic programming
【在 b**y 的大作中提到】
: 请问什么是DP?
|
b**y
发帖数: 13 | 24 谢谢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)
|
p*****2
发帖数: 21240 | 25
我觉得这题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;
|
b**y
发帖数: 13 | 26 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
知道hashtable和trie哪个容易实现排序？
【在 p*****2 的大作中提到】
:
: 我觉得这题trie不是考点。dictionary用hashtable就可以了。考点应该是DP
|
p*****2
发帖数: 21240 | 27
如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
以了。
【在 b**y 的大作中提到】
: 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
: 还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
: 知道hashtable和trie哪个容易实现排序？
|
z****4
发帖数: 194 | 28 trie也不是最优的，最优的是dag
另外
，不
【在 p*****2 的大作中提到】
:
: 如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
: 是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
: 以了。
|
b**y
发帖数: 13 | 29 谢谢楼上zhangchitc，peking 和zyf674 的热心回复，大概的思路有了，不过要补的课很多，剪枝和dag都没用过 |
d******u
发帖数: 397 | 30 DAG-directed acyclic graph??
Why is it optimal? Even better than Hashmap in terms of time?
【在 z****4 的大作中提到】
: trie也不是最优的，最优的是dag
:
: 另外
: ，不
|
|
|
z****4
发帖数: 194 | 31 存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧
【在 d******u 的大作中提到】
: DAG-directed acyclic graph??
: Why is it optimal? Even better than Hashmap in terms of time?
|
d******u
发帖数: 397 | 32 如果collision多的话,hashmap确实很难O(1)
能说一下DAG好在哪里吗？
【在 z****4 的大作中提到】
: 存一整本字典的话，hashmap怎么查？似乎很难做到O(1)吧
|
z****4
发帖数: 194 | 33 dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
全一样的。
【在 d******u 的大作中提到】
: 如果collision多的话,hashmap确实很难O(1)
: 能说一下DAG好在哪里吗？
|
d******u
发帖数: 397 | 34 I see. Thank you !
【在 z****4 的大作中提到】
: dag比trie可以节省space，如果不需要存储每个词的释义而只需要知道有没有这个词的
: 话。比如give和gave可以从v开始收敛到一起，要是trie就是两条路了。查找速度是完
: 全一样的。
|
b**y
发帖数: 13 | 35 实现代码:
// 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;
} |
i**********e
发帖数: 1145 | 36 楼上说了，DP 是最优的。
上次实现的是最容易想到的 backtrack + trie 来剪枝优化。虽然测试了一个字典，不
到一秒就出结果，theoretical worst case复杂度还是exponential 的。
这里给你做参考:
http://www.mitbbs.com/article_t/JobHunting/31926643.html |
t*******e
发帖数: 274 | 37 如果把
(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))))
有什么区别？ |
t*******e
发帖数: 274 | 38 如果把
(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))))
有什么区别？ |
c*****a
发帖数: 808 | |
t*******e
发帖数: 274 | 40 如果把
(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))))
有什么区别？ |
|
|
t*******e
发帖数: 274 | 41 如果把
(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))))
有什么区别？ |
c*****a
发帖数: 808 | |
m******s
发帖数: 204 | 43 请问可否先按词的长度排序，然后在构建Trie时一边加节点一边判断当时的词是否由前
面已加的词组成？
写算法时发现结构很复杂，很多状态要考虑，不知这么思考有无根本上的问题？
请大家见谅把这么老的题拿出来鞭尸。。。 |
r*********n
发帖数: 4553 | 44 我觉得上面各位的解法都忽略了一个重要的条件：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.
: 给你一个词典，找出长度最长的复合单词，怎么解呢，先谢谢了
|
h*******0
发帖数: 270 | 45 没看懂。。 详细点被
【在 r*********n 的大作中提到】
: 我觉得上面各位的解法都忽略了一个重要的条件：sorted
: 显然如果一个词可以分解成其他词的组合，那么这个词一定和其第一个分词靠得很近，
: 比如
: aa
: aabbccaa
: bb
: bbc
: bbbbbb
: cc
: ccbb
|
h*******0
发帖数: 270 | 46 二爷，dp咋做啊？ 求不吝赐教
【在 p*****2 的大作中提到】
:
: 如果只是检查单词在不在字典，我觉得hashtable就挺好吧，会比trie慢吗？但是肯定
: 是比trie浪费空间。这道题我觉得不需要排序，从头开始检查就好。DP＋剪枝应该就可
: 以了。
|
r*********n
发帖数: 4553 | 47 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 的大作中提到】
: 没看懂。。 详细点被
|
m******s
发帖数: 204 | 48 但这样会得到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开头的
|
r*********n
发帖数: 4553 | 49 在确定aa bb 之后一条路是restart，另外一条路是一直下去，所以也有dfs的意思在里
面，并不是greedy algorithm，找最长match。
【在 m******s 的大作中提到】
: 但这样会得到A = aa bbc 然后会得到不是组合的结果。而实际上A = aa bb cc bb...
: 觉得难点在bb之后，如何决定c从头开始还是在bb之后？
|
m******s
发帖数: 204 | 50 同求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
|
|
|
m******s
发帖数: 204 | 51 原题解法似乎不能涵盖所有情况：
aa aabbcc bb bbc cc
把aabbcc拆分成两部分：
(a abbcc) (aa bbcc) (aab bcc) (aabb cc) (aabbc c)
其中没有那一对中的两个都被包含在词典里，但aabbcc可以被分成aa bb cc
【在 c*****a 的大作中提到】
: 这题是cc150里面的啊
|
s**********r
发帖数: 8153 | 52 为啥我记得是150题里的？
貌似我1小时前刚看。。。 |
m******s
发帖数: 204 | 53 原题解法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小时前刚看。。。
|
s**********r
发帖数: 8153 | 54 我只看了题目没看解答，后来找不到题了。。。。
先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
|
m******s
发帖数: 204 | 55 前一个想法需要记录很多无用的中间信息，下面的想法除了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;
} |
