Lintcode171 Anagrams solution 题解

【题目描述】

Given an array of strings, return all groups of strings that are anagrams.

【注】:All inputs will be in lower-case

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

【注】:所有的字符串都只包含小写字母

【题目链接】

www.lintcode.com/en/problem/anagrams/

【题目解析】

所谓“换位词/变位词”就是包含相同字母,但字母顺序可能不同的字符串。比如“abc", "bca", "cab", "acb", "bac", "cba"都互为换位词。

很容易想到,这些换位词如果按字母序排序后都是”abc“,所以可以对原数组中每个字符串自身进行排序,然后出现过两次以上的就是我们要找的字符串。

需要注意的是,要保持原字符串数组不变,那么就需要一个同样大小的数组来存储排序后的每个字符串。

接下来的问题是,如何找出出现两次以上的字符串对应的原字符串,这个用代码比较难以实现,两层for循环的暴力解决会超时。再用一个同样大小的数组标记相应下标位置的原字符串是否为“换位词”,这样需要一边遍历,然后再一边遍历把相应位置的原字符串添加到结果集中。

【参考答案】

www.jiuzhang.com/solutions/anagrams/

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 8,591评论 0 4
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,354评论 0 33
  • 1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不...
    曲终人散Li阅读 8,645评论 0 19
  • 这是个手机普及的年代,各种APP横空出世,手机虽然不怎么换,装的APP却是换来换去。有些APP装了发现不怎么用删掉...
    薄荷草2016阅读 1,800评论 0 0
  • 药命(六) 药房里,孙主任正在详细的看着大海给他的各种资料,还时不时询问大海安克公司这些药的数据来源,以及可靠度,...
    Mr海鲜君的故事阅读 3,430评论 0 0