天天看點

java最短摘要_程式設計之美--最短摘要生成

題目:

Alibaba筆試題:給定一段産品的英文描述,包含M個英文字母,每個英文單詞以空格分隔,無其他标點符号;

再給定N個英文單詞關鍵 字,請說明思路并程式設計實作方法String extractSummary(String description,String[] key words),

目标是找出此産品描述中包含N個關鍵字(每個關鍵詞至少出現一次)的長度最短的子串,作為産品簡介輸出。(不限程式設計語言)20分。

先來看看這些序列:

w0,w1,w2,w3,q0,w4,w5,q1,w6,w7,w8,q0,w9,q1

分析

當初看這道題時,看了好了幾遍都沒看懂。後來總算弄明白:給出的字元串是用其它程式分好詞的,關鍵字元串也是用其它程式分好詞的,而不是按使用者直接輸入的字元串。比如書上給的例子:“微軟亞洲研究院 使命”,不是按空格分成兩個關鍵詞,“微軟亞洲研究院”和“使命”,而是按其它程式分成:“微軟”、“亞洲”、“研究院”和“使命”四個關鍵詞。

“最短摘要”應該是指:包含所有關鍵字(關鍵字不要求按使用者輸入的順序排列)的長度最短的摘要。書上的解法,把“最短摘要”了解成包含所有關鍵字且詞個數最少的摘要。

這個過程要記錄最短文摘的資訊。

這個時間複雜度是 O(N ^ 2 * M)

N 是文檔的長度

M 是關鍵詞數組的大小

總結的滑動視窗法是:

------------------------------------------------------

使用滑動視窗的辦法,找出最短摘要。我們把這個滑動視窗叫做摘要滑動視窗。

摘要滑動視窗左邊界L,右邊界R。

視窗中應該維護的資訊:

視窗中已經周遊過的關鍵字序列----可使用隊列才存儲;

視窗中各個關鍵字出現的個數----可使用hashtable來表示或者數組也行。

[while]

右邊界R向右移動的原則:

目前視窗中不包含所有種類的關鍵字,R向右移動尋找更新的關鍵字。

左邊界L向右移動的原則:

目前視窗中已經包含了所有種類的關鍵字,計算目前摘要長度,并從隊列中拿出一個關鍵字,即L向右移動一個關鍵字;

L與R一直移動下去,一直到R不能往右移動時候,循環結束。

[end while]