[LintCode] Anagrams
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 |
public List<String> anagrams(String[] strs) { // write your code here List<String> res = new ArrayList<String>(); if(strs.length == 0 || strs == null) return res; HashMap<Integer,ArrayList<String>> maps = new HashMap<Integer,ArrayList<String>>(); for(int i = 0 ; i < strs.length; i++) { String s = strs[i]; int[] count = new int[26]; for(int j = 0; j < s.length(); j++) count[s.charAt(j) - 'a']++; int h = hash(count); if(!maps.containsKey(h)) maps.put(h, new ArrayList<String>()); maps.get(h).add(s); } for(List<String> l : maps.values()){ if(l.size() > 1) res.addAll(l); } return res; } public int hash(int[] count) { int hash = 0; int a = 3; int b = 7; for(int i = 0 ; i < count.length; i++) { hash = a*hash + count[i]; a = a * b; } return hash; } |
Leave A Comment