寻找组成字母相同的单词

寻找组成字母相同的单词 这篇文章是对这个帖子的汇总,帖子里的答复都很有意思,真希望ITEye多一些这样的帖子,少一些浮躁和毫无意义的争论。

我把帖子汇总贴在下面:

Write a function that takes as input list of words and prints out groups of words with exactly the same letters, one group per line.

For example,

Given the list:

hat, top, potter, pot, pier, ripe

It would print:

hat

top, pot

potter,

pier, ripe

Since ‘pier’ and ‘ripe’ each have one p, i, e, and r they belong on the same line. Since no other word has the same 6 letters as ‘potter’ it belongs on a line by itself.

Note: The order of the lines does not matter. As long as all words that belong on the same line are grouped together the function is correct.

Please use the following function signature:

void PrintGroupsWithSameLetters(string[] words)

我首先想到的问题解决办法和二楼一样:

构造一个map,key为升序拍好的字母串,value就是出现的单词。

可是,这样多做了一件事。

对,就是给每个单词排序。这件事能否不做?

是不是可以给每一个字母一个编码,让不同字母组合的编码和不相同?后面有同学有类似的思路,回答道:

每个字母对应一个素数, 然后把所有单词响应的素数相乘,然后把结果做比较,结果相同的,说明这个单词和另一个单词有相同的字母。

当然了,素数乘积的办法遭到了驳斥:

不建议用素数乘积做,我之前也想过了这个问题。

比如说一个单词 ZZZZZZ = (101)..101> 2的6次方*….. >2的36次方

想想就知道,这超过了int 的32位。

还没完,之后又有同学有想到:

现根据字符串长度进行分组, 然后再对字符串进行排序。 大体为第一步:归类(长度相等的一类) 第二步:给每个分组中的字符串排序再归类。

呵呵,有点MapReduce的意思哦。

既然提到了映射和化简,那就有可以改进的地方,比如可以按照HashCode的特性来分类。后面还有用二进制数移位等等办法的讨论,实现代码也是Python、Java、Erlang、Groovy等等花样百出。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>