Resolvendo "Grupo de Anagramas"
Tags: dsa, leetcode
Published: 2023-12-27 18:01:24

---
title: Resolvendo "Grupo de Anagramas"
published: true
description: 
tags: #dsa #leetcode
# cover_image: 
# Use a ratio of 100:42 for best results.
# published_at: 2023-12-27 00:23 +0000
---

Hoje vamos resolver mais um leetcode. E, dessa vez, o desafio escolhido é o [Grupo de Anagramas](https://leetcode.com/problems/group-anagrams)

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**

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

Exemplo em imagem:

![Anagrama da palavra alegria](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/swimp1xm93c63ot2tmmg.png)

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.

```python
>>> 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:

```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](https://wiki.python.org/moin/DictionaryKeys).

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.