LeetCode-Anagrams

Anagrams

##题目

####Anagrams

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

Note: All inputs will be in lower-case.

##解题思路
Anagrams为易位构词，其实也很好理解，就是两个单词所包含的字符和数量都是一样的，只是顺序不同。

判断两个单词是不是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类的字符串，这样就可以比较简单的进行分类。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    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[] st=strs[i].toCharArray();
        	Arrays.sort(st);
        	String sts=new String(st);
        	if(map.containsKey(sts))
        	{
        		ArrayList<String> alist=map.get(sts);
        		alist.add(strs[i]);
        		map.put(sts,alist);
        	}else{
        		ArrayList<String> alist=new ArrayList<String>();
        		alist.add(strs[i]);
        		map.put(sts,alist);
        	}

        }

        Iterator iter=map.values().iterator();
        while(iter.hasNext())
        {
        	ArrayList<String> item=(ArrayList<String>)iter.next();
        	if(item.size()>1)
        		res.addAll(item);
        }
        return res;

    }
}

Comments

▲