iTechArt Group - Custom Software Development and Offshore outsourcing
Company
http://www.itechart.com/
Offshore custom software development company iTechArt - Web site and
Content Management Solutions development, CMS consulting: Ektron,
Drupal and DotNetNuke
iTechArt Group provides high
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
Can them be implemented using stacks? Two stacks, one is called ls and
the other is rs.
I agree. Two things are needed, 1st, for each trackable action, a
reverse action should be recorded in order to perform the undo action.
The action itself must be recoreded as well for redo action. 2nd, two
the problem is you need a hash table to maintain all the keywords,:)
because they do not have to be a single characters, or you can store them in
array, but then you need binary search,:)
Vishal 写道:
How about keeping two pointers - startp and endp.
Keep a count of frequencies of keywords
Hash table should give you O(1) insertion and search complexity; which is
what we need, right?
There is no constraint on space complexity, I believe.
On 9/24/07, daizisheng [EMAIL PROTECTED] wrote:
the problem is you need a hash table to maintain all the keywords,:)
because they do not have
Vishal 写道:
Hash table should give you O(1) insertion and search complexity; which
is what we need, right?
There is no constraint on space complexity, I believe.
On 9/24/07, * daizisheng* [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
the problem is you need a hash table to
Another possibility is to first pre-process the keywords into
automaton-like structure (Google for Aho Corasick string matcher), and
then use it over the document. This would probably be helpful only if
the number of keywords is much smaller than the document itself..
On 9/25/07, daizisheng
I am agree with Sticker,
I comes to write exactly what Sticker wrote. ;)
It's O(N^2 / 2) that is 1+2+3+4+5+...+N.
On 9/25/07, Sticker [EMAIL PROTECTED] wrote:
I saw your ideas. Some of them are correct some are not. Here is what
I am thinking.
From the question we know that 1 ≤ M ≤ 100
