接上次的,google 2011校招清华笔试最后一题题目(感觉在考MapReduce思想和动态规划):
KOF游戏中一个大招规则如下:S->T, S与T分别为按键集合。当按键满足一定规则时,可以连续按出大招,即连招。
例如招数表如下:ABC->D, BCD->E, DE->F, EF->G。那么,当按键顺序为:ABC->D->E->F->G 时,可以输出一个最长连招。
现给定一组招数,求出其中的最长连招。如可以无限连招,输出一个特定数字,否则输出最长连招长度。
我的思路:
对于一招S->T, 假设T的长度为1(不为1也可以,写法稍有变化), S长度为m。如果这一招可以连上之前的招数,那么它的m前缀一定等于某一个或多个其它招数的m后缀。这样,我们可以先扫描一遍所有招数,看看有多少种m;然后通过map过程对每个招数建立各个m后缀的索引,然后通过reduce过程,把对应的后缀与前缀的招数连起来,形成一张图。剩下的步骤,就可以利用动态规划求最长链或环了。
代码如下,夜里写的,没怎么写注释。。。对于复杂度,如果招数的数量N远大于招数的长度M的话,那么时间复杂度应该是O(N)的。