学步园

题目

原文

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

Note: All inputs will be in lower-case.

译文

输入一组字符串，输出所有重组字相同的字符串。

解答

首先，要理解 anagram 的含义。"abc" 和 ''bca", ''cba"都是anagram, "abc" 和 "abcd" 不是anagram。

之后，当我看到lower-case的时候，一下子理解为" 所有输入都是小写字母"，如此一来，直接想到只要借助一个大小26 的字符数组，来做统计，就能够完成题目。

假设有n个字符串，我要统计字符串每个字符出现的次数，所以需要二维数组，行表示第i个字符串，列表示字符。

int n =strs.length;
int[][] count = new int[n][26];
for(int i=0;i<n;i++){
       String temp = strs[i];
       char[] c = temp.toCharArray();
       for(int j=0;j<c.length;j++){
            count[i][c[j]-'a']++;
        }
}

之后只要比较这个数组的哪些行相等即可了。只要有行相等就插入给最后的链表，

boolean[] id  = new boolean[n];
ArrayList<String> s = new ArrayList<String>();
for(int i=0;i<n;i++){
    //只要出现过重复的就不看了
    if(id[i]==true){
        continue;
    }
    int j;
    int sign =1;
    s.add(strs[i]);
        //查看之后的是否和目前这个相同
    for(j=i+1;j<n;j++){
        boolean identical = true;
        for(int k=0;k<25;k++){
            if(count[i][k]!=count[j][k]){
                identical=false;
                break;
            }
                                                                                                                                                                                                                                                                                                                                                            
        }
                //如果出现的字符都相同，就加入答案
        if(identical == true){
            s.add(strs[j]);
            id[j]=true;
            sign=0;
            continue;
        }
    }
        //如果没出现过，删除事先加入进去的这个
    if(sign==1){
        s.remove(0);
    }
}

说时迟，纳什快，我这就兴高采烈地submit，结果。。。time exceed，原因是碰到大数据超时。

思考一下用的时间：设有n个字符串，每个字符串n个字符。生成数组O(nm), 之后比较需要O(n^2)的时间。

的确不是很理想。参考了讨论，发觉的确有个我遗漏的方式 HashMap，思路是既然 重组字 最后重组后的字符串都相同，那么就把它作为Map 的key ，然后value类型很关键，如果只是一个字符串，放不下重复的；那么就放一个链表，把所有相同的都串起来。最后输出串的超过2的。

代码如下(论坛上的，我觉得非常简洁)：

public class Solution {
public ArrayList<String> anagrams(String[] strs) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<String> anagram = new ArrayList<String>();
    HashMap<String,ArrayList<String>> list = new  
            HashMap<String,ArrayList<String>>();
    for (String str: strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        if (list.containsKey(key)) {
            list.get(key).add(str);
        } else {
            list.put(key,new ArrayList<String>
                        (Arrays.asList(str)));
        }
    }
    for (ArrayList<String> test:list.values()) {
        if (test.size()>1) {
            anagram.addAll(test);
        }
    }
    return anagram;
}
}

时间上来说，对于每个字符，快排O(mlgm)，list查找1；最差情况下，都相同，arraylist加入新元素,需要平均n/2的次数，n个字符，总共就是O(n*(mlgm+n/2)),和前面方法一个数量级；但是一般情况，不会如此,基本O(nmlgm),在m远小于n的情况下，第二种方法更加好。

PS 这道题目，要把所有重组字相同的组都给输出，而不是只输出一组。