careercup-高等难度 18.7
18.7 给定一组单词,编写一个程序,找出其中的最长单词,且该单词由这组单词中的其他单词组合而成。 解法: 原题 给定字符串,以及一个字典,判断字符串是否能够拆分为字段中的单词。例如,字段为{hello,world},字符串为hellohelloworld,则可以拆分为hello,hello,world,都是字典中的单词。 分析 这个题目唤作“分词问题”,略显宽泛。只是想提及这个问题,这是在自然语言处理,搜索引擎等等领域中,非常基础的一个问题,解决的方法也比较多,相对比较成熟,不过这仍旧是一个值得进一步探索的问题。那我们先从这个简单的题目入手,看看如何处理题目中这个问题。 最直接的思路就是递归,很简单。我们考虑每一个前缀,是否在字典中?如果在,则递归处理剩下的字串,如果不在;则考虑其他前缀。示例代码如下: 递归的方法实现: 但是这样会有很多重复的查找: 这个题目的处理,上期的题目是很相似的。在递归子问题中,找重复的子问题。也非常明显,如下图(图片来自GeeksforGeeks)所示: 如果使用动态规划的方法: bool wordBreak(string s, unordered_set...