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