买哪种减肥药带回国送人比较好# Fashion - 美丽时尚
c*g
1 楼
网上看到一道题 求O(n)的解法. n是document中的word数
You have a dictionary, D, that stores the positions of words in a document
by mapping words (strings) to positions in the document (arrays of ints.)
You also have a list of words, L. Your job is to find the shortest sequence
of words in the document that contains all the words in L.
E.g., if the document is "a b a c d x b a", then
D["a"] = [0 2 7]
D["b"] = [1 6]
...
If we are given that L=["a", "c", "x"]
Then we should return the start and end point of the shortest sequence that
contains all words in L, which is (2, 5). The best solution is in O(n)
complexity.
You have a dictionary, D, that stores the positions of words in a document
by mapping words (strings) to positions in the document (arrays of ints.)
You also have a list of words, L. Your job is to find the shortest sequence
of words in the document that contains all the words in L.
E.g., if the document is "a b a c d x b a", then
D["a"] = [0 2 7]
D["b"] = [1 6]
...
If we are given that L=["a", "c", "x"]
Then we should return the start and end point of the shortest sequence that
contains all words in L, which is (2, 5). The best solution is in O(n)
complexity.