Java simple 23ms solution, beats 97%, no sorting, constructed a new Anag class


  • 1
    B
    public class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            Map<Anag, Integer> map = new HashMap<Anag, Integer>();
            List<List<String>> res = new ArrayList<List<String>>();
            int size = 0;
            for (String str : strs) {
                Anag cur = new Anag(str);
                if (!map.containsKey(cur)) {
                    map.put(cur, size++);
                    List<String> curList = new ArrayList<String>();
                    curList.add(str);
                    res.add(curList);
                } else {
                    List<String> curList = res.get(map.get(cur));
                    curList.add(str);
                }
            }
            return res;
        }
        
        //Anag: a class that maintains the equality of Anagram, used in HashMap
        private static class Anag {
            int[] table;
            public Anag(String str) {
                table = new int[26];
                if (str != null && str.length() > 0) {
                    char[] ca = str.toCharArray();
                    for (char c : ca) {
                        table[c - 'a']++;
                    }
                }
            }
            @Override
            public int hashCode() {
            	int i = 1;
            	int prime = 31;
            	for (int num : table) {
            		i = prime * i + num;
            	}
            	return i;
            }
            @Override
            public boolean equals(Object oj) {
                if (oj instanceof Anag) {
                    Anag that = (Anag)oj;
                    for (int i = 0; i < this.table.length; i++) {
                        if (this.table[i] != that.table[i]) return false;
                    }
                    return true;
                }
                return false;
            }
        } 
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.