“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Grouping of letter ectopic words

You are given an array of strings, and you are asked to combine alphabetic anagram words. The list of results can be returned in any order.

An anagram is a new word created by rearranging the letters of the source word so that all the letters in the source word are used exactly once.

Example:

Input: STRS = [” eat “, “tea”, “tan”, “ate” and “NAT” and “bat”]

Output: [[” bat “], [” NAT “, “tan”], [” ate “, “eat”, “tea”]]

Tip:

1 <= strs.length <= 104

0 <= strs[i].length <= 100

STRS [I] contains only lowercase letters

Their thinking

First of all, we need to understand the concept of anagram: a few words are anagram words, which are a subset of a set of letters (letter repeatable) arranged in full; At the same time, the set of different letters (including the number of different letters) are mutually exclusive.

For example,” eat”,”tea”,”ate” given in the example, and “tae”,”aet”,”eta” not shown are elements of the set of letters [A, e, t], which are all alphabetic allographs of each other.

With an understanding of the concept of letter heterotopic, it is much easier to achieve classification. We can use Map to take each letter heterotopic as Key and the list of letter heterotopic as Value to achieve classification.

The following two ideas are given for implementation:

Sort + Map

However, since the number and type of letters between letters are the same, it is not difficult to find that the results of character sorting of the letters of letters are exactly the same (similar to minimum lexicographic order).

With this property, we can use the string obtained by sorting words as the unique identifier of each set of alphabetic allotopic words, namely the Key of the Map.

The code implementation is as follows:

func groupAnagrams(strs []string)[] []string { 
    wordMap := map[string] []string{} 
    for _, str := range strs { 
        key := SortString(str) 
        wordMap[key] = append(wordMap[key], str) 
    } 
    ans := make([] []string.0.len(wordMap)) 
    for _, v := range wordMap { 
        ans = append(ans, v) 
    } 
    return ans 
} 
func SortString(s string) string { 
    ret := strings.Split(s, "") 
    sort.Strings(ret) 
    return strings.Join(ret, "")}Copy the code

Submit screenshots:

Letter quantity statistics + Map

Although the above sorting is used as the Key AC, the sorting time complexity is O(klogk), where K is the length of a letter. When the length of a letter is large, it takes a long time to generate a Key. The Key uniqueness can theoretically be achieved by O(n), so the above code can be optimized.

In this case, space is used to exchange time, and the number of occurrences of each word is counted by opening another Map. Finally, letters and corresponding numbers are combined into a unique string of heteronyms for each letter as Key. The time complexity of the Key generation operation is reduced from O(klogk) to O(k).

The code implementation is as follows:

func groupAnagrams(strs []string)[] []string { 
    wordMap := map[string] []string{} 
    for _, str := range strs { 
        key := MakeKey(str) 
        wordMap[key] = append(wordMap[key], str) 
    } 
    ans := make([] []string.0.len(wordMap)) 
    for _, v := range wordMap { 
        ans = append(ans, v) 
    } 
    return ans 
} 
func MakeKey(s string) string { 
    nums := [26]int{}
    for _, b := range s {
        nums[b-'a'] + +}var ret string
    for _, num := range nums {
        ret += fmt.Sprintf("%d", num) + "- >"
    }
    return ret
}
Copy the code