25号阿里笔试第一题,alikealibaba,递归解法
void recursionFind(const string& str, const set<string>& dict, vector<vector<int> >& result, int cur, vector<int> index) { for (int i = cur; i <= str.size(); ++i) { string temp = str.substr(cur, i - cur); if (dict.find(temp) != dict.end()) { if (i < str.size()) { index.push_back(i); recursionFind(str, dict, result, i, index); index.pop_back(); } else { result.push_back(index); break; } } } } void mincut(const string& str, const set<string>& dict) { if (str.size() == 0) return; int cur = 0; vector<vector<int> > result; vector<int> index({ 0 }); for (int i = cur; i <= str.size(); ++i) { string temp = str.substr(cur, i - cur); if (dict.find(temp) != dict.end()) { if (i < str.size()) { index.push_back(i); recursionFind(str, dict, result, i, index); index.pop_back(); } else { result.push_back(index); break; } } } if (result.size() == 0) cout << "n/a" << endl; else { int min = 0; for (int i = 1; i < result.size(); ++i) { if (result[i].size() < result[min].si敏感词 = i; } string target = ""; for (int i = 0; ; ++i) { if (i + 1 < result[min].size()) { target += str.substr(result[min][i], result[min][i + 1] - result[min][i]) + " "; } else { target += str.substr(result[min][i]); break; } } cout << target << endl; } return; } 当搜索空间比较大时,本解法就会比较慢。 对于result中的每个可行解,我保存字符串分割的下标
#阿里巴巴#