Resolvendo "Grupo de Anagramas"

Hoje vamos resolver mais um leetcode. E, dessa vez, o desafio escolhido é o Grupo de Anagramas

Nesse desafio, precisamos agrupar os diferentes anagramas passados como entrada da função.

Um anagrama é uma palavra que é formada a partir das letras de uma outra palavra. Por exemplo: alegria e alergia e regalia. Todas essas palavras são anagramas.

O desafio é agrupar todos os anagramas. A entrada da função terá uma lista de diferentes palavras que podem ou não ser anagramas. Esse agrupamento deve ser uma lista de listas.

Exemplo do site:

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

Escrevendo o algoritmo

Esse é um problema de nível médio, o que significa que a solução não vem tão fácil. Muitas dessas questões tem diversas soluções, e o que difere elas é uma menor complexidade te tempo/espaço e, também, ciclomática.

Vamos dividir o problema em partes:

• Iterar sobre a lista de palavras;
• Para cada palavra, vamos calcular a chave desse anagrama (já vamos explicar o que é isso que chamei de chave);
• Usaremos essa chave para agrupar os anagramas;
• Agruparemos os anagramas em um dicionário, que casa com o conceito de ter uma chave. O valor de cada chave será uma lista de anagramas;
• Retornaremos apenas os valores do dicionário, que vai ser uma lista de listas.

Calculando a chave

O cálculo da chave é essencial pra esse algoritmo. Ela vai servir para agruparmos as palavras que são anagramas.

O desafio tem uma limitação de que as palavras são todas minúsculas, o que facilita nosso algoritmo.

A chave é construída calculando quais letras são similares em cada palavra. Vamos usar como exemplo as palavras amor e roma:

A M O R
R O M A

{"A": 1, "M": 1, "O": 1, "R": 1}

Exemplo em imagem:

Ignorando a ordem das letras de ambas as palavras, teremos dicionários com as mesmas chaves e valores, o que nos leva a anagramas.

Existe uma forma mais fácil de calcular essa chave.
As palavras são formadas apenas por letras minúsculas, então temos 26 possibilidades de letras e ocorrências delas, correto?

Come essa informação em mente, podemos criar uma lista de 26 posições e, para cada posição ordinal da letra, incrementar o número de ocorrências dela.

>>> alphabet = [0] * 26
>>> key = ord("m") - ord("a")
>>> alphabet[key] += 1
>>> alphabet
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Ao repetir esse algoritmo, obteremos um array com a quantidade de cada letra. Para as palavras propostas, o array será o mesmo, resultando na nossa chave.

Escrevendo o código

A solução do problema em Python:

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        for word in strs:
            alphabet = [0] * 26 # 26 letters, a to z
            for letter in word:
                alphabet[ord(letter) - ord("a")] += 1
            anagrams[tuple(alphabet)].append(word)

        return anagrams.values()

Explicando o código em partes:

• O defaultdict é essencial para salvar as palavras em grupos. Um agrupamento nesse caso é uma lista de valores associados a uma chave.
• Iteramos na lista de palavras;
• Para cada palavra, criamos uma lista do alfabeto, que será nossa chave;
• Incrementamos a posição ordinal de cada letra;
• Usamos esse valor como chave do dicionário anagrams;
• A chave é convertida pra tupla porque em Python a chave precisa ser um valor hasheable.

Observe o uso de append no dicionário. Essa instrução só funciona porque estamos usando defaultdict, que nos economiza criar uma lista vazia quando a chave do dicionário ainda não existe.

E, por fim, retornamos os valores do dicionário, a lista de lista com as palavras agrupadas.

Complexidade de tempo e espaço

Tempo: A pior complexidade de tempo desse algoritmo é percorrer a lista de palavras e, para cada palavra, percorrer todas as letras dela. Isso gera uma complexidade O(N X M) onde N é o número de palavras e M é o número de letras de cada uma das palavras.

Espaço: A complexidade de espaço é um pouco mais difícil de definir. É O(N), onde o N pode variar entre ser o tamanho da lista do alfabeto (26 posições) ou o tamanho do anagrama. Quanto mais palavras no input, maior vai ser o tamanho do dicionário de palavras agrupadas.

Conclusão

Eu acredito que esse desafio é considerado de nível médio porque é necessário ter um momento de inspiração pra entender que a chave que falamos anteriormente é um ponto crucial pra solução do problema.

Espero que você tenha aprendido algo novo com esse texto, e eu gostaria muito de ter seu feedback nos comentários.