Leetcode - Pairs of Songs With Total Durations Divisible by 60

Leetcode - Group Anagrams

violet posted @ Apr 07, 2020 01:03:28 AM in 算法 with tags Algorithm Golang count sort , 337 阅读

https://leetcode.com/problems/group-anagrams/

Given an array of strings, group anagrams together.

Example:

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

1. Count frequency of letters in every word with count sort

2. Iterate the count from the beginning and compose another sorted string

3. Use a hash, key is sorted string, value is collecting original words

func groupAnagrams(strs []string) [][]string {
    count := make([]int, 26)
    hash := map[string][]string{}
    for _, w := range strs {
        for i := 0; i < len(w); i++ {
            count[w[i]-'a']++
        }
        str := []byte{}
        for i := 0; i < 26; i++ {
            if count[i] != 0 {
                val := count[i]
                for val > 0 {
                    str = append(str, byte(i)+'a')
                    val--
                }                
                count[i] = 0
            }
        }
        hash[string(str)] = append(hash[string(str)], w)
    }
    result := [][]string{}
    for _, val := range hash {
        result = append(result, val)
    }
    
    return result
}