Thursday, July 24, 2014

Anagrams

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

Note: All inputs will be in lower-case.

Anagrams 指对于不同string,他们不同char的出现次数一样。我们可以用一个26size的array来记录每个string各种char出现的次数,用它来计算对应每个string的hash value,如果是anagrams,value也会相同。把结果放进HashMap,对于每个value,如果对应的string个数大于1,就加进结果里。
public class Solution {
    //Time: O(n * m) m is average length of each string
    public ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> res = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return res;
        }
        
        HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
        for (int i = 0; i < strs.length; i++) {
            int[] count = new int[26];
            String s = strs[i];
            for (int j = 0; j < s.length(); j++) {
                count[s.charAt(j) - 'a']++;
            }
            int val = getValue(count);
            if (!map.containsKey(val)) {
                ArrayList<String> tmp = new ArrayList<String>();
                tmp.add(s);
                map.put(val, tmp);
            } else {
                ArrayList<String> tmp = map.get(val);
                tmp.add(s);
                map.put(val, tmp);
            }
        }
        
        for (int i : map.keySet()) {
            if (map.get(i).size() > 1) {
                res.addAll(map.get(i));
            }
        }
        return res;
    }
    
    private int getValue(int[] count) {
        int val = 0;
        for (int i = 0; i < count.length; i++) {
            val = val * 31 + count[i];
        }
        return val;
    }
}

No comments:

Post a Comment