https://segmentfault.com/a/1190000003740929
http://www.programcreek.com/2014/04/leetcode-anagrams-java/
Given an array of strings, group anagrams together.
For example, given:
Return:
["eat", "tea", "tan", "ate", "nat", "bat"],Return:
[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
Note:
- For the return value, each inner list's elements must follow the lexicographic order.
- All inputs will be in lower-case.
public List<String> anagrams(String[] strs) { ArrayList<String> result = new ArrayList<String>(); if(strs == null || strs.length == 0) return result; HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>(); for(int i=0; i<strs.length; i++){ char[] arr = strs[i].toCharArray(); Arrays.sort(arr); String t = String.valueOf(arr); if(map.get(t) == null){ ArrayList<Integer> l = new ArrayList<Integer>(); l.add(i); map.put(t, l); }else{ map.get(t).add(i); } } for(ArrayList<Integer> l: map.values()){ if(l.size() > 1){ for(Integer i: l){ result.add(strs[i]); } } } return result; } |
public List<List<String>> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) return new ArrayList<List<String>>(); Map<String, List<String>> map = new HashMap<String, List<String>>(); Arrays.sort(strs); for (String s : strs) { char[] ca = s.toCharArray(); Arrays.sort(ca); String keyStr = String.valueOf(ca); if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>()); map.get(keyStr).add(s); } return new ArrayList<List<String>>(map.values());//\\ }
Code from http://www.darrensunny.me/leetcode-anagrams/
public ArrayList<String> anagrams(String[] strs) {
ArrayList<String> res = new ArrayList<String>();
if(strs == null || strs.length == 0)
return res;
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
for(int i=0;i<strs.length;i++)
{
char[] charArr = strs[i].toCharArray();
Arrays.sort(charArr);
String str = new String(charArr);
if(map.containsKey(str))
{
map.get(str).add(strs[i]);
}
else
{
ArrayList<String> list = new ArrayList<String>();
list.add(strs[i]);
map.put(str,list);
}
}
Iterator iter = map.values().iterator();
while(iter.hasNext())
{
ArrayList<String> item = (ArrayList<String>)iter.next();
if(item.size()>1)
res.addAll(item);
}
return res;
}
https://segmentfault.com/a/1190000003740929
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for(String str : strs){
// 将单词按字母排序
char[] carr = str.toCharArray();
Arrays.sort(carr);
String key = new String(carr);
List<String> list = map.get(key);
if(list == null){
list = new ArrayList<String>();
}
list.add(str);
map.put(key, list);
}
List<List<String>> res = new ArrayList<List<String>>();
// 将列表按单词排序
for(String key : map.keySet()){
List<String> curr = map.get(key);
Collections.sort(curr);
res.add(curr);
}
return res;
}- def groupAnagrams(self, strs):
ans = []dic = collections.defaultdict(list)for s in strs:dic[str(sorted(s))].append(s)for value in dic.values():ans.append(sorted(value))return ans
A list of numbers are given. We need to find the total number of groups in which the digits of each number have same frequency.
For example if numbers are:
1
10
303
330
For example if numbers are:
1
10
303
330
There are 3 groups:
G1={1}has one 1.
G2={10} has one 1 and one 0.
G3={330, 303} has one 0 and two 3s
G1={1}has one 1.
G2={10} has one 1 and one 0.
G3={330, 303} has one 0 and two 3s
A variation of Group Anagrams?
Just sort the digits of each number and de-dupe them
class AnagramComparator implements Comparator<String> {
public String sortChars(String s) {
char[] content= s.toCharArray();
Arrays.sort(content);
return new String(content);
}
public int compare(String sl, String s2) {
return sortChars(sl).compareTo(sortChars(s2));
}
}
Arrays.sort(array, new AnagramComparator());
This algorithm will take O(n log(n)) time.
void sort(String[] array) {
HashMaplist<String, String> maplist = new HashMaplist<String, String>();
/* Group words by anagram */
for (String s : array) {
String key= sortChars(s);
maplist.put(key, s);
}
// Convert hash table to array*
int index = 0;
for (String key: maplist.keySet()) {
Arraylist<String> list= maplist.get(key);
for (String t : list) {
array[index] = t;
index++;
}
}
}
/*HashMapList<String, Integer> is a HashMap that maps from Strings to
* Arraylist<Integer>. See appendix for implementation. */
Read full article from My Own Notes: Leetcode: Anagrams
