c***g
发帖数: 472 | 1 given one article, and a set of keywords
find the shortest length part which contain all the keywords
how to do that?
After translated, it will be: given a sequence, how to
find a shortest substring that contains all the items required. Example: a s
equence "abaccdefgacel" and a set of key words "a" "c", "d" and "e". The sho
rtest substring contianing all of the key words is "accde". Find one of such
shortest substrings. | j********e
发帖数: 7 | 2 Let me try:
step 1: traverse the string once, and count the occurance of each key
characters in the search string: i.e. a:3, c:3, d:1, e:1
step 2 : Recursion
/*"count" maps key characters to the # of occurance*/
/*"stringPath" is the longest string path so far containing all key characters
*/
void checkShortest(deque& stringPath, Map& count)
{
char head = stringPath.front();
char tail = stringPath.back();
/*Head character is not a key character*/
/*Or it is a key character, and h | s****u
发帖数: 118 | 3 are你sure就是一个字母的key？
而且看不懂你的什么意思 -_-
characters
【在 j********e 的大作中提到】
: Let me try:
: step 1: traverse the string once, and count the occurance of each key
: characters in the search string: i.e. a:3, c:3, d:1, e:1
: step 2 : Recursion
: /*"count" maps key characters to the # of occurance*/
: /*"stringPath" is the longest string path so far containing all key characters
: */
: void checkShortest(deque& stringPath, Map& count)
: {
: char head = stringPath.front();
| j********e
发帖数: 7 | 4 I just worked off the simplified example in the original post. For string
keyword, the same token applies.
【在 s****u 的大作中提到】
: are你sure就是一个字母的key？
: 而且看不懂你的什么意思 -_-
:
: characters
| s**********0
发帖数: 5 | 5 Definition: for single keyword X(consists of one or more characters),
*f_start1(X)
means the earliest poistion of the first character of X in the article.
*f_end1(X)
means the latest position of the first character of X in the article.
*f_start2(X)
means the earliest poistion of the last character of X in the article.
*f_end2(X)
means the latest position of the last character of X in the article.
For n keywords X1,X2,X3...,Xn, suppose the starting and ending position
of the shortest sub-article | i********r
发帖数: 131 | 6 One solution: O(N) time complexity
str is the input string,
K is the set of characters to be covered.
1. Create a structure to remember best result
Create a solution set R, which includes 0 solution.
A solution includes: a) starting index b) a bitmap showing which
characters are already covered.
2. scan through the string, for every character ch (with index = i)
2.1 if ch is not in K, do nothing and move on
2.2 if ch is in K, initialize a solution and put in R
s.index = i, ch | s****u
发帖数: 118 | 7 ft，character的key的话，简单的贪心就可以O(n)
【在 i********r 的大作中提到】
: One solution: O(N) time complexity
: str is the input string,
: K is the set of characters to be covered.
: 1. Create a structure to remember best result
: Create a solution set R, which includes 0 solution.
: A solution includes: a) starting index b) a bitmap showing which
: characters are already covered.
: 2. scan through the string, for every character ch (with index = i)
: 2.1 if ch is not in K, do nothing and move on
: 2.2 if ch is in K, initialize a solution and put in R
|
|
