I think hash method is ok, at lease in expectation way it's O(n) why not use it? it's very effeciently
I think there should be some worst case O(n) algorithm, but it will be more complex and not as effecient as the above one in practise Sticker 写道: > Declare: this question is originally from Google. The original form > is: given a document, how to find a shortest summary containing all > the key words. After translated, it will be: given a sequence, how to > find a shortest substring that contains all the items required. > Example: a sequence "abaccdefgacel" and a set of key words "a", "c", > "d" and "e". The shortest substring contianing all of the key words is > "accde". Find one of such shortest substrings. In the original > question, there is time complexity boundary O(N), where N is the > length of the sequence. > > To me, this problem is rather questionable. So far my solution > requires a hash table that gives no conflict and can locate a key word > in O(1) time. Otherwise the time complexity will definitely be related > to the number of key words. > > Does anyone have idea for a O(N) algorithm to solve this problem? > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
