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中的每个可行解，我保存字符串分割的下标