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.
Top comments (0)