首页 > 代码库 > Leetcode: Anagrams
Leetcode: Anagrams
Given an array of strings, return all groups of strings that are anagrams.Note: All inputs will be in lower-case.
Analysis: 这个题简单的版本是判断两个单词是不是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的大小。实现代码如下：
Notice: 遇到这一个错误：
Input:["",""] Output:[] Expected:["",""]
原因在于第８行，我以前写的是：String afterprocess = temp.toString(); 看来对“”不管用，改成String afterprocess = new String(temp);就对了，原因？
还有第１９行的做法，第２１行的做法我第一次用，需要掌握
1 public class Solution { 2 public ArrayList<String> anagrams(String[] strs) { 3 HashMap<String, ArrayList<String>> anagramlist = new HashMap<String, ArrayList<String>>(); 4 ArrayList<String> results = new ArrayList<String>(); 5 if (strs == null || strs.length ==0) return results; 6 for (String single : strs) { 7 char[] temp = single.toCharArray(); 8 java.util.Arrays.sort(temp); 9 String afterprocess = new String(temp);10 if (anagramlist.containsKey(afterprocess)) {11 anagramlist.get(afterprocess).add(single);12 }13 else {14 ArrayList<String> list = new ArrayList<String>();15 list.add(single);16 anagramlist.put(afterprocess, list);17 }18 }19 for (ArrayList<String> each : anagramlist.values()) {20 if (each.size() > 1) {21 results.addAll(each);22 }23 }24 return results;25 }26 }