解决单词链的最佳方法
我正在尝试解决这个在CodeEval上的问题。
这个挑战让我们玩一个叫“单词链”的游戏，规则是玩家需要想出一个单词，这个单词的首字母要和前一个单词的尾字母相同。挑战的目标是找出可以从给定单词列表中形成的最长单词链的长度。
举个例子：
Input:
soup,sugar,peas,rice
Ouput:
4
解释：我们可以形成一个4个单词的链，像这样：“soup->peas->sugar->rice”。
限制条件：
- 单词列表的长度在[4, 35]之间。
- 列表中的每个单词都是由随机的小写字母组成，长度在[3, 7]个字母之间。
- 列表中没有重复的单词。
我的尝试：我的方法是把单词看作一个图，每个单词代表一个节点，如果一个单词的最后一个字母和另一个单词的第一个字母相同，就在这两个单词之间画一条（有向）边。
接下来，我从每个节点出发，运行广度优先搜索（bfs），计算从这个节点出发能到达的最远节点的长度。最后的结果就是所有节点中能得到的最大值。
但是这个方法没有让我得到满分。因此，我的问题是，如何才能正确而高效地解决这个问题呢？
3 个回答
可以查看这个链接提到的解决方案：在核心Java中的单词链
这个页面提供了一个在核心Java中的解决方案，主要步骤如下：
- 将字典中的单词加载到内存中，针对特定的单词长度
- 根据给定的单词，从内存中获取下一个符合条件的单词列表
还有一种使用Map/Reduce的Hadoop框架的方法，详细内容可以在这个链接找到：使用Map-Reduce的单词链
可以参考这里提到的解决方案：检测矩阵乘法是否可能
你的问题的解决方法基本上是一样的。你需要创建一个有向图，对于每个单词，从第一个字母到最后一个字母之间画一条边。
然后在这个图中找到一个欧拉路径（http://en.wikipedia.org/wiki/Euler_path）。
编辑：我看到你不确定是否要使用所有单词，你需要在图中找到最长的路径（http://en.wikipedia.org/wiki/Longest_path_problem）。这个问题是NP完全的。
因为我的声望低于50，所以我不能发表评论...
如果单词总数少于20个，我们可以用动态规划和位掩码来解决这个问题。我们可以创建一个叫做dp的数组，大小是dp[20][1<<20]。这里的dp[i][j]表示你现在在第i个位置，并且你已经访问了位掩码j所代表的单词。
如果单词数量超过20个，我还没有好的想法。也许我们需要用一些随机算法，可能会有帮助……。
我的想法是使用深度优先搜索（dfs）并加上一些优化，因为35个单词并不算太多。我觉得这样就足够解决这个问题了。