阿里巴巴笔试的一道算法题。该怎么解决

阿里巴巴笔试的一道算法题。
只记得大约是这样子的：
M为字符组成的文章，N是关键字（M>N）,找出包含所有关键字N的最短子串。

C/C++ code

String extractSummary(String description, String[] keywords)

编程语言不限。当时想了一半，没有比较好的解法，求助。

[解决办法]
string extractSummary(string description, string (&keywords)[N])
{
ifstream in(description.c_str());
if(!in){cout<<"error!"<<endl;return 0;}
string s,minstr;
int minLen,row=1;
bool ishit=true;;
while(in>>s)
{
for(int i=0;i<N;i++)
{
if((s.find(keywords[i]))==string::npos){
ishit=false;
break;
}
}
if(ishit){
if(row==1) {minLen=s.size();minstr=s;}
else{
if(s.size()<minLen) {
minLen=s.size();
minstr=s;
}
}
row++;
}

}
return minstr;
}
[解决办法]
字符串的比较就不说了,这个实现的算法很多,就说说查找最小段的问题，其实这就是一个最短摘要问题，很多搜索会用到这一点。

解决起来就很简单：

1 反复读入字符串，直到碰到关键字（可以用set或unordered_set）。

2 更新该关键字字符串最近出现的位置。

3 若已经找到所有的关键字，则根据这些关键字的位置最小/最大值，计算摘要长度。

可以用set来维护这些位置值。

（实际上，只要求维护位置的最小值，还可以自行实现一个堆结构，节省空间。）

根据位置值计算长度，需要先计算出分词后的字符串，在未分词的字符串的位置。

4 记录长度最短的摘要

若有m个关键字，待查询字符串有n个，时间复杂度大概为：O(n*log m)
[解决办法]

C/C++ code

4abbbcddcdbcddbadcbbcd ddc dc ddbcddc请按任意键继续. . .
[解决办法]
探讨

只记得大约是这样子的：
M为字符组成的文章，N是关键字（M>N）,找出包含所有关键字N的最短子串。


C/C++ code

String extractSummary(String description, String[] keywords)



编程语言不限。当时想了一半，没有比较好的解法，求助。

[解决办法]
探讨


文章是M个单词还是M个字符？

[解决办法]
探讨


C/C++ code
4
abbbcddcdbcddbadcb
bcd ddc dc dd
bcddc
请按任意键继续. . .



C/C++ code
#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef struct record
{
    record(con……
 

 

查看更多 下一篇