2018阿里秋招C/C++研发编程题——字符串处理

78 阅读 0 评论 52 点赞

我是靠谱客的博主轻松电脑，最近开发中收集的这篇文章主要介绍2018阿里秋招C/C++研发编程题——字符串处理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定一个字符串S和有效单词的字典D，请确定可以插入到S中的最小空格数，使得最终的字符串完全由D中的有效单词组成，并输出解。

如果没有解则应该输出n/a

例如

输入
S = "ilikealibaba"
D = ["i", "like", "ali", "liba", "baba", "alibaba"]
Example Output:

输出
"i like alibaba"

解释：
字符串S可能被字典D这样拆分
"i like ali baba"
"i like alibaba"
很显然，第二个查分结果是空格数最少的解。

编译器版本: gcc 4.8.4

请使用标准输入输出(stdin，stdout) ；请把所有程序写在一个文件里，勿使用已禁用图形、文件、网络、系统相关的头文件和操作，如sys/stat.h , unistd.h , curl/curl.h , process.h

时间限制: 3S (C/C++以外的语言为: 5 S) 内存限制: 128M (C/C++以外的语言为: 640 M)

输入:

第一行为字符串S 第二行为输入一个整数表示字典中字符串的个数其余行为字典中的内容

输出:

输出为加入空格后的字符串

输入范例:

ilikealibaba

6

i

like

ali

liba

baba

alibaba

输出范例:

i like alibaba

我的思路：

1、每次循环截取S的子串，从最大子串开始截，每次循环结束截掉最后一个字符

2、从字典D里查找子串，如果找到，则将找到的子串存到静态数组里，然后将S截掉找到的子串，递归调用截取函数。

3、如果截取完找到的子串之后S为长度为0，则递归结束，输出静态数组里元素。

4、如果字典里找不到S的任何子串，则退出，输出n/a。

欢迎批评指正：

#include <set>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void mincut(const string& str, const set<string>& dict)
{
int i;
static vector<string> vstr;
static int flag = 0;
if (flag == 0) {
for (i = 0;i <str.size();++i) {
auto tmp = str.substr(0, str.size() - i);
auto setit = dict.find(tmp);
if (setit != dict.end()) {
vstr.push_back(*setit);
string sub = str.substr(str.size() - i, str.size());
if (sub.size() == 0) {
flag = 1;
for (auto it = vstr.begin();it != vstr.end();++it) {
cout << *it;
if(it != vstr.end() - 1)
cout << " ";
}
return;
}
mincut(sub, dict);
}
}
if (flag == 0) {
flag = 1;
cout << "n/a";
return;
}
}
}
int main(int argc, const char * argv[])
{
string strS;
string dictStr;
int nDict;
set<string> dict;
cin >> strS;
cin >> nDict;
for (int i = 0; i < nDict; i++)
{
cin >> dictStr;
dict.insert(dictStr);
}
mincut(strS, dict);
return 0;
}