第一题和之前在leetcode上刷过的一题Word Break II有很多类似之处,感觉就是那道题改变了下?所以侥幸过了。
第二题没看懂题意,感觉自己很菜,不知有没有大神过了。这一贴一下第一题的代码:
#include <string>
#include <cstdio>
#include <set>
#include <algorithm>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
/***
* ilikealibaba
* i like ali liba baba alibaba
**/
unordered_set<string> wordict;
unordered_map<string, vector<string>> map;
vector<string> wordscut(string s)
{
if (map.find(s) != map.end())
return map[s];
vector<string> sens;
for (int pos = s.size() - 1; pos >= 0; --pos)
{
string word = s.substr(pos);
if (wordict.find(word) != wordict.end())
{
if (pos == 0) sens.push_back(word);
else
{
vector<string> subSens = wordscut(s.substr(0, pos));
for (auto subSens : subSens)
sens.push_back(subSens + " " + word);
}
}
}
map[s] = sens;
return sens;
}
vector<string> helper(string s, const set<string> & Dict)
{
wordict.insert(Dict.cbegin(), Dict.cend());
return wordscut(s);
}
bool compare(string str1, string str2)
{
return str1.length() < str2.length();
}
void mincut(const string& str, const set<string>& dict)
{
int slen = str.length();
int size = dict.size();
if (size == 0)
{
cout << "n/a" << endl;
return;
}
vector<string> res = helper(str, dict);
if (res.empty())
{
cout << "n/a" << endl;
return;
}
sort(res.begin(), res.end(), compare);
cout << res[0] << 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);
}
mincut(strS, dict);
return 0;
}