18.7 给定一组单词，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。
解法：
原题
给定字符串，以及一个字典，判断字符串是否能够拆分为字段中的单词。例如，字段为{hello，world}，字符串为hellohelloworld，则可以拆分为hello,hello,world，都是字典中的单词。
分析
这个题目唤作“分词问题”，略显宽泛。只是想提及这个问题，这是在自然语言处理，搜索引擎等等领域中，非常基础的一个问题，解决的方法也比较多，相对比较成熟，不过这仍旧是一个值得进一步探索的问题。那我们先从这个简单的题目入手，看看如何处理题目中这个问题。 最直接的思路就是递归，很简单。我们考虑每一个前缀，是否在字典中？如果在，则递归处理剩下的字串，如果不在；则考虑其他前缀。示例代码如下：
递归的方法实现：
但是这样会有很多重复的查找：
这个题目的处理，上期的题目是很相似的。在递归子问题中，找重复的子问题。也非常明显，如下图(图片来自GeeksforGeeks)所示：
如果使用动态规划的方法：
bool wordBreak(string s, unordered_set<string> &dict) {
if(dict.empty()||s.empty())
return false;
unordered_map<string,bool> mp;
auto iter=dict.begin();
while(iter!=dict.end())
{
mp[*iter]=true;
iter++;
}
return canBuildWord(s,mp);
}
bool canBuildWord(string s,unordered_map<string,bool> &mp)
{
if(mp.find(s)!=mp.end())
return mp[s];
for(int i=;i<=s.length();i++)
{
string left=s.substr(,i);
string right=s.substr(i);
if(mp.find(left)!=mp.end()&&mp[left]==true&&canBuildWord(right,mp))
return true;
}
mp[s]=false;
return false;
}
其中使用动态规划的方法缓存了多次调用之间的结果。如果该字符串在map中没有找到，那么将该字符串插入到map中，并将其值置为false，如果下次还是查找该字符串且该字符串在map中，并且值为false，则可以直接返回其在map中存放的值。