? ? ?Alibaba筆試題：給定一段產品的英文描述，包含M個英文字母，每個英文單詞以空格分隔，無其他標點符號；再給定N個英文單詞關鍵字，請說明思路并編程實現方法String extractSummary(String description,String[] key words)目標是找出此產品描述中包含N個關鍵字（每個關鍵詞至少出現一次）的長度最短的子串，作為產品簡介輸出。（不限編程語言）20分。

　　解：簡化題目：從一個字符串A中找出包含另一個字符串B所有字母的最小字串。（比A短，并每個字母只出現一次；這里先排除了關鍵詞多次出現的情況，這種情況只需稍微改動即可），考慮使用兩個指針p、q指向A起始位置，遍歷指針p，

1、使得q到p之間包含了B中的所有字母。這時可以是使用一個數組來記錄p中走過A中遇到B中字母出現的次數。這樣當所有字母全非0的時候，即可。這時未能保證q到p是以*p結尾子句中包含所有字母的最短的一個。

2、此時走動q指針，另q走到恰好q到p是以*p結尾子句中包含所有字母的最短的一個。

如A=dccdaadc B=cda

經過第一步，q指向A[0]，p指向A[4] 計數數組 221 字串dccda并不是以A[4]結尾子句中最短的包含B的子串

然后，走q指針。走過A[1]時，計數數組121，即此時還是包含了B（ccda），所有繼續再走；直到A[2]時，計數數組為111，下一個將出現不能包含B的全部字母所以此時A[2]~A[4]為以A[4]結尾子句中包含所有字母的最短的一個。

3、然后記錄相應信息。q走過一個，使得q~p未能包含全部的B，這時又回到了第一步，直至整個字符串檢測完畢。

這里的代碼并未考慮關鍵字出現多次的情況。這種情況只需要稍做改動即可；

1 #include <iostream> 2 3 using namespace std; 4 5 6 //p指向的單詞（空格結尾或'\0'），在關鍵詞組中是否存在，存在則相應計數；當所有關鍵字計數 7 //不為0,即包含了所有的關鍵字了,以*flag回傳1 8 //返回單詞的后一個位置(若為'\0'則返回'\0') 9 char* countkw_add(int cnt[], char *p, char * kw[], int n, int *falg) // 10 { 11 char *q; 12 char tmp[50]={0}; 13 q = tmp; 14 while(*p && *p!=' ')*q++ = *p++; 15 16 *q = '\0'; 17 18 for (int i=0; i<n; i++) 19 { 20 if (strcmp(tmp, kw[i])==0) 21 { 22 cnt[i]++; 23 for(int j=0; j<n; ++j) 24 { 25 if (!cnt[j]) 26 { 27 break; 28 } 29 } 30 if (j==n) 31 { 32 *falg = 1; //包含了所有的關鍵字 33 } 34 break; //找到 35 } 36 } 37 while(*p && *p++!=' '); // 38 39 return p; 40 } 41 //由于只有計數數組cnt的數據全非零時才調用此函數 42 //p指向的單詞（空格結尾或'\0'），在關鍵詞組中是否存在，存在則減去相應計數；當存在關鍵字計數 43 //不為0,即未包含所有的關鍵字了,以*flag回傳0 44 //返回單詞的后一個位置(若為'\0'則返回'\0') 45 char* countkw_sub(int cnt[], char *p, char * kw[], int n, int *falg) 46 { 47 char *q; 48 char tmp[50]={0}; 49 q = tmp; 50 while(*p && *p!=' ')*q++ = *p++; 51 52 *q = '\0'; 53 54 for (int i=0; i<n; i++) 55 { 56 57 if (strcmp(tmp, kw[i])==0) 58 { 59 cnt[i]--; 60 61 if (cnt[i]==0) 62 { 63 *falg = 0; //缺關鍵字kw[i] 64 } 65 break; //找到 66 } 67 } 68 while(*p && *p++!=' '); // 69 70 return p; 71 } 72 73 void extractSummery(char *des, char * keywords[], int n, char **beg, char **end) 74 { 75 char *p,*q; 76 77 int *cnt; 78 int minlen=strlen(des); // 79 *beg = NULL; 80 *end = NULL; 81 82 cnt = (int *)malloc(sizeof(int)*n); 83 memset(cnt, 0, sizeof(int)*n); 84 85 86 q= des; 87 while(*q!='\0' && *q==' ')q++; 88 89 p = q; 90 int fulled=0; 91 92 while(*p!='\0') 93 { 94 95 p = countkw_add(cnt,p,keywords,n, &fulled); 96 97 while(*p && *p==' ')p++; 98 99 if (fulled) //包含了所有的關鍵字 100 { 101 char *tmp; 102 tmp = q; 103 while(fulled) 104 { 105 q = tmp; //記錄上一次 106 tmp= countkw_sub(cnt,tmp,keywords,n, &fulled); 107 } 108 109 if (p-q<minlen) //發現更小的，則更新 110 { 111 minlen = p-q; 112 *beg = q; 113 *end = p; 114 } 115 //while(*q && *q!=' ')q++; 116 q = tmp; 117 while(*q && *q==' ')q++; //指向下一個詞 118 } 119 120 121 122 } 123 } 124 125 126 127 128 int main() 129 { 130 char des[] = "aefo aec egne a se a fe a aec ve fjfj as lel"; 131 132 char *kw[] = {"aec" ,"a", "fjfj"}; 133 char *b,*e; 134 135 extractSummery(des,kw,3,&b,&e); 136 137 for(char *p=b; p<e; p++) 138 { 139 cout<<*p; 140 } 141 142 cout<<endl; 143 144 return 0; 145 }

?

---恢復內容結束---

轉載于:https://www.cnblogs.com/legendmaner/archive/2013/03/17/2965030.html

總結

以上是生活随笔為你收集整理的Alibaba笔试题：根据关键字求最短摘要字串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。