Code Kata:Word Chains

又做一个Kata题目。这回是Kata 19，Word Chains，即要在字典中寻找一个单词序列，头和尾由输入决定，相邻的单词必须只能相差一个字母。例如下面是一个从cat到dog的单词链：

cat->cot->cog->dog

这个题目我想不到什么特别巧妙的算法，只能暴力搜索。但是因为输入数据量非常大，如果用递归的话会导致栈溢出，所以改用队列。最后的性能还马马虎虎。Kata上说作者的原始解答跑得很慢，用他提供的字典找从"ruby"到"code"的单词链需要90s，而"code"到"ruby"要一个小时。他后来改进了算法，上面这两个例子都可以在0.5s到1s内完成。由此可见算法的确是影响程序性能的第一要素。我的程序基本上差不多，从"ruby"到"code"耗时0.5s，"code"到"ruby"稍微长一点，大概1.8s，可见算法还有改进的余地。

wordchain.py

还是老办法，放到googlepages上。

现在觉得python确实好用，代码写起来很快，主要得归功于库的强大，特别是一些常用数据结构，比如list,dictionary(hash table)，都是作为内建数据类型支持的。python里面唯一让我有些不爽的就是string。想要把一个string排序就得先把string转换为list,对list排序后再重新转换为string。文档上说这是因为string是imutable object，不可变对象，而list的sort方法会改变对象。那为什么不给string专门实现一个sort方法呢？可能Guido van Rossum觉得用list过渡一下进行排序也没什么不好的，再加上对string进行sort不算是特别常用的方法，就懒得实现了。