微软面试题之 "单词的划分"-白红宇的个人博客

微软面试题之 "单词的划分"

发布日期：2021-05-09 04:09:42 浏览次数：15 分类：博客文章

本文共 1615 字，大约阅读时间需要 5 分钟。

Problem

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。

出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

Input

第一行为一整数T，表示有T组测试数据。

每组测试数据第一行为一字符串。(长度小于256)

第二行为一整数N。（1<=N<=100）

以下N行，每行一个单词。

Output

一个整数，表示字符串可以被划分成的最少的单词数。

Sample Input

1 realityour 5 real reality it your our

Sample Output

code:

#include <cstdio>

#include <cstring>

#include <set>

#include <functional>

using namespace std;

enum { MAX_LEN = 256 };

struct sless : public binary_function<const char*, const char*, bool>

{

bool operator()(const char* s1, const char* s2) const

{

return strcmp(s1, s2) < 0;

}

};

int split_string(char* s, const set<const char*, sless>& words)

{

if (s == 0)

return 0;

int m[MAX_LEN] = {0};

int len = strlen(s);

for (int i = 0; i < len; ++i)

{

char ch = s[i+1];

s[i+1] = 0;

if (words.find(s) != words.end())

m[i] = 1;

else

{

int minimum = INT_MAX;

for (int j = i; j > 0; --j)

{

if (m[j-1] != 0 && words.find(s+j) != words.end())

minimum = min(m[j-1]+1, minimum);

}

m[i] = minimum;

}

s[i+1] = ch;

}

return m[len-1];

}

int main()

{

#if 0 // for lazy testing

char s[] = "realityour";

const char* words[] =

{

"real",

"reality",

"it",

"your",

"our",

};

set<const char*, sless> ws;

for (int i = 0; words[i] != 0; ++i)

ws.insert(words[i]);

int result = split_string(s, ws);

printf("result: %d\n", result);

#endif

int size;

scanf("%d", &size);

for (int i = 0; i < size; ++i)

{

char s[MAX_LEN] = {0};

scanf("%s", s);

int num;

scanf("%d", &num);

set<const char*, sless> ws;

for (int j = 0; j < num; ++j)

{

char* in = new char[128];

memset(in, 0, 128);

scanf("%s", in);

ws.insert(in);

}

printf("%d\n", split_string(s, ws));

}

上一篇：出租司机给我上的MBA课

下一篇：微软面试题之 "Longest Common Sequence"

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！