给定字符串，以及一个字典，判断字符串是否能够拆分为字段中的单词。例如，字段为{hello，world}，字符串为hellohelloworld，则可以拆分为hello,hello,world，都是字典中的单词。这是陈利人微博上的一道题目，很简单，但是使用场景确实很多。其实我们可以发现，在计算机中很多听起来牛B的技术，它的原理确不是很复杂。比如对于数据挖掘和机器学习中的很多算法都是基于贝叶斯算法的，概率论中我们都学过。贝叶斯算法介绍。
下面直接复制的一种解法，因为对于递归的解法我们都可以实现，就直接贴出代码。看到有人给出了图示和动归的实现，就无节操的复制过来，对自己的切词分词知识体形进行补充。对于切次与分词的介绍，请看另一篇简介：http://blog.csdn.net/zwan0518/article/details/8494982
解决办法之递归解法：
bool solution(string str, set<string> set){
int size = str.size();
if (size == 0) return true;
for(int i = 1; i <= size; i ++){
if(set.find(str.substr(0, i)) != set.end() &&
solution(str.substr(i, size - i), set)){
cout << "cut: " << str.substr(0, i) << endl;
return true;
}
}
return false;
}
因为是采用的递归实现，所以打印出切词是倒序打印出来的，就是从后面往前打印。如果需要正序，那么可以把切词结果add进一个栈，然后再打印。
解决办法之DP解法：
对于递归问题很多重复子问题，比如对字串(i, j)的判断就会出现两遍，第一遍是外层遍历，第二遍则是递归的时候又要判断一遍。在递归子问题中，找重复的子问题。也非常明显，如下图(图片来自GeeksforGeeks)所示：
所以，通过动态规划的方法，可以通过有较大幅度的提升，同样，这个题目与前面的每一个状态都有关系的，所以，是一个二重循环，时间复杂度为O(n^2)。示例代码如下：
除此之外，这个问题的方法是非常多的，大家还有什么思路呢？欢迎大家展开思路互动讨论。