Group Anagrams Leetcode


#1

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

#2

Sort each string and see if there’s an available key in the map, if it is add them to the list. The code basically groups all strings in their sorted form.

func groupAnagrams(strs []string) [][]string {
    aMap := make(map[string][]string, 0)
    result := [][]string{}
    if len(strs)==0{ return result}
    for i:=0;i<len(strs);i++{
        r := []rune(strs[i])
        sort.Sort(sortRunes(r))
        s := string(r)
        if val, ok := aMap[s]; ok {
           val = append(val, strs[i])
           aMap[s] = val
        } else {
            list := []string{strs[i]}
            aMap[s] = list
        }
    }
    
    for _, v := range aMap{
        result = append(result, v)
    }
    
    return result
}

type sortRunes []rune
func (sr sortRunes) Len() int{ return len(sr) }
func (sr sortRunes) Swap(i, j int) {sr[i], sr[j] = sr[j], sr[i]}
func (sr sortRunes) Less(i, j int) bool { return sr[i] < sr[j]}

#3

Similar approach to sort and group together.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
          List<List<String>> result = new ArrayList<>();
          if(strs==null || strs.length==0) return result;
          HashMap<String, List<String>> map = new HashMap<>();
          for(String s : strs){
              char[] sch = s.toCharArray();
              Arrays.sort(sch);
              String sort = String.valueOf(sch);
              if(!map.containsKey(sort))
                  map.put(sort, new ArrayList<String>());
              map.get(sort).add(s);
          }
        
        for(String key : map.keySet()){
            result.add(map.get(key));
        }
        
        return result;
    } 
}