本文共 2086 字，大约阅读时间需要 6 分钟。
题目：
给定一个字符串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" 很显然，第二个查分结果是空格数最少的解。
思路：
首先，先构建一个str.size() x str.size() 大小的图，存储第str.substr(i, j - i + 1)子串是否在dict字典中，若是，则置1，否则置0。
其次，用dfs算法，遍历图，找到包含1最少的通路。
代码：
#include考试的时候，自己卡在了dfs函数上， 辣鸡！！！#include #include #include using namespace std;void dfs(vector > &flag, int i, int j, vector &curRet, vector &minRet);void mincut(const string& str, const set & dict){ int sizeOfStr = str.size(); vector > flag(sizeOfStr, vector (sizeOfStr, 0)); int i, j; string subStr = ""; for (i = 0; i < sizeOfStr; ++i){ for (j = 1; j <= sizeOfStr - i; ++j){//从i开始的j个字符 subStr = str.substr(i, j); if (dict.find(subStr) != dict.end()) flag[i][i + j - 1] = 1; } } for (i = 0; i < sizeOfStr; ++i){ for (j = 0; j < sizeOfStr; ++j){ cout << flag[i][j] << ' '; } cout << endl; } vector curRet; vector minRet(str.size()); dfs(flag, 0, 0, curRet, minRet); if (!minRet.empty()){ int start = 0; vector ::iterator iter = minRet.begin(); for (; iter != minRet.end() - 1; ++iter){ cout << str.substr(start, *iter - start + 1) << ' '; start = *iter + 1; } cout << str.substr(start, *iter - start + 1) << endl; } else cout << "n/a" << endl;}void dfs(vector > &flag, int i, int j, vector &curRet , vector &minRet){ if (j == flag.size()){//如果到了字符串str的尾部 if (curRet.size() < minRet.size()){//如果当前路径中1的个数小于最小路径 minRet.clear();//清空最小路径 minRet = curRet;//重置最小路径 } } for (; j < flag.size(); ++j){ if (flag[i][j] == 1){ curRet.push_back(j); dfs(flag, j + 1, j + 1, curRet, minRet); curRet.pop_back(); } }}int main(int argc, const char * argv[]){ string strS; string dictStr; int nDict; set dict; cin >> strS; cin >> nDict; for (int i = 0; i < nDict; i++) { cin >> dictStr; dict.insert(dictStr); } mincut(strS, dict); return 0;}
转载地址：http://hxnii.baihongyu.com/