m******a
发帖数: 84 | 1 Design an algorithm to find the shortest substring in a synopsis such that
it contains all the words in a provided list.
比如list 是: ["aaa", "aab"]
synopsis是： "aaabaaab"
应该返回 "aabaaa"
这个因为word 之前有可能overlap, 请教各位有什么好办法么？ | c*******a
发帖数: 1879 | 2 一天到晚就做这些乌托邦的东西， 有什么鸡巴用？
【在 m******a 的大作中提到】
: Design an algorithm to find the shortest substring in a synopsis such that
: it contains all the words in a provided list.
: 比如list 是: ["aaa", "aab"]
: synopsis是： "aaabaaab"
: 应该返回 "aabaaa"
: 这个因为word 之前有可能overlap, 请教各位有什么好办法么？
| h*********n
发帖数: 11319 | 3 sliding window + KMP
O(N * K), K是字典大小
【在 m******a 的大作中提到】
: Design an algorithm to find the shortest substring in a synopsis such that
: it contains all the words in a provided list.
: 比如list 是: ["aaa", "aab"]
: synopsis是： "aaabaaab"
: 应该返回 "aabaaa"
: 这个因为word 之前有可能overlap, 请教各位有什么好办法么？
|
|
