好吧,我承认,这次我偷懒了。
这个Kata要做的是单词变换,输入两个单词,输出最小变换次数。
看例子:
输入:cat dog
输出:3
具体的变换过程:
cat
cot
cog
dog
每次变换只能改变一个字母,变换后必须也是一个合法单词。
之所以偷懒,是因为我发现这次真的是一个纯算法题,我对纯算法一向兴趣不大,所以就没有写。不过简单说下思路吧:
思路
既然要输出最小变换次数,那无非就是深搜和广搜了。单词长度有限,变换次数应该不会太多,所以方案是广搜。
搜索之前需要先生成图,每个节点是一个单词,每条边表示这个单词经过一次变换可以到达另一个单词,所以构造图需要O(n2)的时间。搜索的话复杂度是O(n),所以总复杂度还是O(n2),如果能提前构造好图,那会快很多。
至于优化,广搜没什么好优化的,第一个找到的肯定就是最短路径。
大概就是这样,写完想想似乎难度也不大, 就是遍历生成图,然后标准广搜即可,注意处理无限循环。