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

给定一个字符串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”
很显然，第二个查分结果是空格数最少的解。

AC代码如下

#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

int fun(string str1, string str2, int a) {
int count = 0;
int i = a; int j = 0;
while (i < str1.size() && j < str2.size() && str1[i] == str2[j]) {
        count++;
        i++; j++;
    }
if (((i==str1.size())&&(j==str2.size())) || j == str2.size())
return count;
return 0;
}

void mincut(const string& str, const set<string>& dict)
{
vector<string> res;
if (str.empty() || dict.empty()) {
cout << "n/a" << endl;
return;
    }
int i = 0;
for (; i < str.size();i++) {
char c = str[i];
set<string>::iterator it = dict.begin();
for (; it != dict.end(); it++) {
if ((*it)[0] == c)
break;
        }

int maxlen = 0;
while (it != dict.end() && (*it)[0] == c) {
int len = fun(str, *it, i);
if (maxlen < len)
                maxlen = len;
            it++;
        }
if (maxlen == 0) {
cout << "n/a" << endl;
return;
        }
string temp = str.substr(i, maxlen);
// cout << temp << " ";
        res.push_back(temp);
        i += maxlen-1;
    }
if (i == str.size())
    {
for (auto x : res)
cout << x << " ";
cout << endl;
    }
else
cout << "n/a" << endl;
}


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);
    }

//for (auto x : dict)
// cout << x << " ";
    mincut(strS, dict);

return 0;
}