49. Group Anagrams

Stanislav Gumeniuk включен в leetcode leetcode-problem

2020.04.07 255 слов Пару мгновений

Содержание

Решение задачи 49 “Group Anagrams” с LeetCode.

Условие задачи

Дан массив строк. Необходимо сгруппировать анаграммы вместе.

Замечение:

все буквы в нижнем регистре
порядок сортировки неважен

пример

1
2
3
4
5
6
7


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

Решение

Отсортировать массив =)

Идея алгоритма:

Написать функцию, которая по заданному слову, возвращает слово с этиме же буквами, но буквы отсортированы по возрастанию.

Создать коллекцию, где ключом будет слово после сортировки букв, а значением - массив слов, состоящий из букв этого слова.

Пройтись по всем исходным словам, получить сортировку букв в слове - добавить слово в соответствующий элемент коллекции.

А потом просто создать результирующий массив массивов строк. Пройтись по коллекции , забирая каждый массив и добавляя его в результирующий.

Кратко: сгруппировать слова по буквам из которых они состоят.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


func groupAnagrams(strs []string) [][]string {
    words := make(map[string][]string,0)
    for idx := range strs {
        jdx := orderLetter(strs[idx])
        if _, ok:= words[jdx];!ok {
            words[jdx] = make([]string,0)
        }
        words[jdx] = append(words[jdx] ,strs[idx])
    } 
    res := make([][]string,0)

    for idx := range words{
        res = append(res,words[idx])
    }
    
    return res
}

func orderLetter(s string) string {
    o := []byte(s)
    
    for idx := 0; idx<len(o);idx++ {
        k := idx
        for jdx:=idx-1;jdx>=0;jdx-- {
            if o[jdx]>o[k] {
                tmp := byte(o[jdx])
                o[jdx] = byte(o[k])
                o[k] = tmp
                k = jdx
            }
        }
    }
    return string(o)
}