Kata19

好吧，我承认，这次我偷懒了。

这个Kata要做的是单词变换，输入两个单词，输出最小变换次数。

看例子：

输入：cat dog

输出：3

具体的变换过程：

cat
cot
cog
dog

每次变换只能改变一个字母，变换后必须也是一个合法单词。

之所以偷懒，是因为我发现这次真的是一个纯算法题，我对纯算法一向兴趣不大，所以就没有写。不过简单说下思路吧：

思路

既然要输出最小变换次数，那无非就是深搜和广搜了。单词长度有限，变换次数应该不会太多，所以方案是广搜。

搜索之前需要先生成图，每个节点是一个单词，每条边表示这个单词经过一次变换可以到达另一个单词，所以构造图需要O(n^{2)的时间。搜索的话复杂度是O(n)，所以总复杂度还是O(n}2)，如果能提前构造好图，那会快很多。

至于优化，广搜没什么好优化的，第一个找到的肯定就是最短路径。

大概就是这样，写完想想似乎难度也不大， 就是遍历生成图，然后标准广搜即可，注意处理无限循环。