Kata06地址

前几天事情比较多，Kata没有按照一天一个的进度完成。做之前问了一下小伙伴，他说这次是个算法题，挺麻烦。我听完就是心头一紧，这才第6个Kata就要搞算法，那后面岂不是没法做下去了。

直到看完题目我才松了一口气，以这个作者的尿性就不可能出纯算法题嘛！

任务

这次的任务是从一串单词中找到所有异构单词。好吧我也不知道这么翻译对不对，反正化学上学过异构我就叫它异构了。

异构简单来说就是组成元素相同但是结构不同，比如说fresher和refresh就是一对异构单词。

我们的目标就是找出输入单词中的所有异构单词。

这题乍一看上去还是挺唬人的，似乎一下就会想到什么公共子序列啊逆序对啊K（看）M（毛）P（片）算法啊这些东西，很遗憾的是这作者装得不像，还在文章结尾说

大家好我用ruby实现了一个hack版本可以在i7的电脑上1.8秒执行完成哦

我一看这个输入列表有30W+个单词，我就明白他啥意思了，这题根本不是算法题，就是个脑筋急转弯。

思路

思路其实很简单，关键是别掉进算法的圈套。

简单来说，我们需要一个hash函数，这个函数对于异构单词的hash结果是相同的，我采用的方法是计算单词中的所有字符以及每个字符的出现次数，然后用这个信息构建一个字符串当作结果。

举例来说，fresher中出现了5个字母：fresh，出现次数分别是：12211，我们可以按照字典序构造一个字符串：e2f1h1r2s1，这就是hash结果。我们可以对refresh应用同样的过程，由于最后会按照字典序排序，所以消除了字符出现位置对结果的影响。

这个函数搞定之后下面就简单了，直接用结果当作dict的key，value是一个array，存储这个key对应的所有字符串，这些字符串都是异构的。

代码

仍然是我喜欢的Python，只有10行哦：

import collections

all_results = {}

with open("wordlist.txt") as f:
    for i in f.readlines():
        temp = i.strip()
        count_list = list(i)
        temp_list = list(set(temp))
        all_results.setdefault("".join([j + str(count_list.count(j)) for j in temp_list]), []).append(temp)

这段代码在我的电脑上执行时间大概是3.6秒，不过我的是i5，这段代码性能瓶颈主要都是CPU运算，所以换成i7的话应该不输作者的1.8秒。

总结

我最喜欢的就是这类旁门左道，又好玩又高效，何乐而不为呢？不过最近感觉是该捡捡算法了，等21个Kata全部做完就开始做算法题，基础还是不能丢啊。