原题链接:http://oj.leetcode.com/problems/anagrams/这是一道很经典的面试题了,在cc150里面也有,就是把一个数组按照易位构词分类。易位构词其实也很好理解,就是两个单词所包含的字符和数量都是一样的,只是顺序不同。这个题简单的版本是判断两个单词是不是anagram,一般来说有两种方法。第一种方法是用hashmap,key是字符,value是出现的次数,如果两个单词构成的hashmap相同,那么就是anagram。实现起来就是用一个构建hashmap,然后另一个在前面的hashmap中逐个去除,最后如果hashmap为空,即返回true。这个方法时间复杂度是O(m+n),m,n分别是两个单词的长度。而空间复杂度是O(字符集的大小)。第二种方法是将两个单词排序,如果排序之后结果相同,就说明两个单词是anagram。这种方法的时间复杂度取决于排序算法,一般排序算法是O(nlogn),如果字符集够小,也可以用线性的排序算法。不过总体来说,如果是判断两个单词的,第一种方法要直接简单一些。接下来我们看看这道题,是在很多字符串里面按照anagram分类,如果用hashmap的方法,然后两两匹配,在分组会比较麻烦。而如果用排序的方法则有一个很大的优势,就是排序后的字符串可以作为一个key,也就是某一个class的id,如此只要对每一个字符串排序,然后建立一个hashmap,key是排序后的串,而value是所有属于这个key类的字符串,这样就可以比较简单的进行分类。假设我们有n个字符串,字符串最大长度是k,那么该算法的时间复杂度是O(nklogk),其中O(klogk)是对每一个字符串排序(如果用线性算法也可以提高)。空间复杂度则是O(nk),即hashmap的大小。实现代码如下:public ArrayList<String> anagrams(String[] strs) {
ArrayList<String> res = new ArrayList<String>();
if(strs == null || strs.length == 0)
return res;
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
for(int i=0;i<strs.length;i++)
{
char[] charArr = strs[i].toCharArray();
Arrays.sort(charArr);
String str = new String(charArr);
if(map.containsKey(str))
{
map.get(str).add(strs[i]);
}
else
{
ArrayList<String> list = new ArrayList<String>();
list.add(strs[i]);
map.put(str,list);
}
}
Iterator iter = map.values().iterator();
while(iter.hasNext())
{
ArrayList<String> item = (ArrayList<String>)iter.next();
if(item.size()>1)
res.addAll(item);
}
return res;
}
理清了思路,实现起来还是比较简单的,这道题考察排序,hashmap,字符串处理,比较全面,在面试中非常常见,大家一定要熟悉哈。
分享到:
相关推荐
Leetcode-解决方案-CSharp ***此存储库将包含 C# 中许多 Leetcode 问题的解决方案 收集雨水 - Leetcode 42 (Hard) 文本对齐 - Leetcode 68(硬) 买卖股票的最佳时机 III - Leetcode 123 (Hard) 买卖股票的最佳时机 ...
leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo 中的problems文件夹 使用1.two-sum.js案例导出解决方案 module . exports = { // ignore: true, fn : ...
Leetcode-练习 领英面试问题: 亚马逊面试问题 二和中 有效括号简单 轻松合并两个排序列表 两个链表的交集很容易 有效的字谜容易 二和 II - 输入数组排序中 旋转图像介质 在字符串 II 介质中反转单词 格雷码中号 ...
Anagrams :简单的#hashtable问题。 BalancedBinaryTree :简单的#balance #tree问题。 BestTimetoBuyandSellStock :简单的问题。 BestTimetoBuyandSellStockII :简单的问题。 BestTimetoBuyandSellStockIII : ...
vscode提交leetcode 我的leetcode练习笔记 结构 代码在根路径中,每个cpp文件都是一个问题的解决方案 有关特定问题的解决方案的一些说明在目录中。 我使用的工具 我使用扩展来测试和调试本地并提交我确定我的解决...
Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree Inorder Traversal 栈 递归 Single Number 异或 Copy List with Random Pointer...
groupAnagrams ( String [] strs ) { if (strs == null || strs . length == 0 ) return null ; Map< String , List< String > > map = new HashMap< String , List< String > > (); Arrays . sort(strs...
Anagrams in a String Pattern: two points 双指针是这样的模式:两个指针朝着左右方向移动(双指针分为同向双指针和异向双指针),直到他们有一个或是两个都满足某种条件。 使用双指针的优势:若只用一个指针,需多...
颜色分类leetcode leetcode.etc My solutions of the problems in Online judge website, leetcode, lintcode, etc. leetcode: 13 problems solved lintcode: 49 problems ...Anagrams(比较字符串) E
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
leetcode中国 我自己的leetcode刷题记录 ###[20150920] Valid Palindrome Implement strStr() ...Anagrams 字符串处理,map Simplify Path,字符串处理,stack Length of Last Word,字符串处理.细节题 Rever
给定字符串数组,实现groupAnagrams(strs)将字谜合并在一起并将其作为数组返回 解决方案:实现基于字母计数的散列算法,因此字谜将返回相同的散列。 遍历字符串,获取它们的散列并将它们添加到存储在字典中的字谜组...
LeetCode438_Find_All_Anagrams_in_String 438题目:给定一个字符串s和一个非空字符串p,字符串全部由小写字母子组成。 在S中找出所有p对应的anagrams(颠倒)字符串的子串,返回这些子串的起始索引 如s="cbaebabacd...
加油站 leetcode 力码 ...anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift Leetcode\ma
leetcode 性能javascript_algorithms Javascript 中各种算法的实现。 所有问题都有单元测试覆盖。 为什么是 JavaScript? 它是我目前最强大的语言,考虑到 V8 取得的令人印象深刻的进步,我认为 Javascript 拥有美好...
leetcode 2 和 c 力码 运行时统计: 前 0-20% : 9 次前 20-40% : 3 次前 40-60% : 4 次前 60-80% : 2 次前 80-100% : 16 次总计:接受 33 个问题 问题: 49. 组字谜 中等的 给定一个字符串数组,将字谜组合在一起。 ...
lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...
1. 题目 编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。...链接:https://leetcode-cn.com/problems/group-anagrams-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明
anagrams 两个乱序字符串的比较 lint55 compare-string和group string都是同型题目 int79-LCS lintcode上的79题 寻找最长公共字串 lintcode 138-Subarray-Sum integer-arr 整型数组 值得回顾的题 41-first-missing-...