Competitive-programming/hashmaps/group-anagrams.py at main · AlyssonCaputti/Competitive-programming · GitHub

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
35
36
37
38
39
40
"""
Problema:   Group Anagrams
Fonte:      LeetCode 49 - https://leetcode.com/problems/group-anagrams/
Nivel:      Medium
Tecnica:    hashmap, strings

Enunciado:
    Dada uma lista de strings, agrupe os anagramas. Anagramas sao palavras
    formadas pelas mesmas letras em ordem diferente. A ordem dos grupos e dos
    itens dentro do grupo nao importa.

Exemplo:
    ["eat","tea","tan","ate","nat","bat"]
        ->  [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Dica:
    Duas palavras sao anagramas se as letras ordenadas sao iguais. Use isso
    (a string ordenada) como chave de um dicionario.
"""
from typing import List


def group_anagrams(strs: List[str]) -> List[List[str]]:
    # implemente aqui
    pass


# --- testes ---
def _normaliza(grupos):
    # ordena pra comparar sem depender da ordem
    return sorted(sorted(g) for g in grupos)


if __name__ == "__main__":
    r1 = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    assert _normaliza(r1) == _normaliza([["eat", "tea", "ate"], ["tan", "nat"], ["bat"]])

    assert _normaliza(group_anagrams([""])) == [[""]]
    assert _normaliza(group_anagrams(["a"])) == [["a"]]
    print("todos os testes passaram")