24 de Março
Agrupar anagramas
Como perceber que o ponto principal não e o mapa em si, mas a escolha de uma chave canonica que represente o grupo.
Mapa Hash Intermediario 18 min TypeScript
Dado um array de strings strs, agrupe os anagramas juntos. Você pode retornar a resposta em qualquer ordem.
Exemplo:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
O que perceber antes de codar
- O problema não pede para comparar palavra por palavra manualmente.
- O desafio real e decidir qual chave representa um grupo de anagramas.
- Se a chave estiver errada, o hash map não salva a solução.
Erros comuns
- usar a string original como chave e acabar separando anagramas
- pensar no hash map como resposta completa e não como estrutura de agrupamento
Passo 1 — Tirar o foco da ordem original
eat e tea não parecem iguais na superficie.
Mas pertencem ao mesmo grupo.
Isso quer dizer que a chave do agrupamento não pode depender da ordem original.
Passo 2 — Escrever uma versão inicial correta
Uma versão inicial possível e, para cada palavra, procurar se ela cabe em algum grupo existente:
export function groupAnagrams(strs: string[]): string[][] {
const groups: string[][] = []
for (const word of strs) {
const normalizedWord = word.split('').sort().join('')
let placed = false
for (const group of groups) {
const normalizedGroup = group[0].split('').sort().join('')
if (normalizedGroup === normalizedWord) {
group.push(word)
placed = true
break
}
}
if (!placed) {
groups.push([word])
}
}
return groups
}
Funciona. Mas você fica procurando grupo por grupo.
Passo 3 — Perguntar qual e a chave canonica
O mapa hash só ajuda se palavras equivalentes gerarem a mesma chave.
Uma chave simples aqui e:
- ordenar os caracteres da palavra
Assim:
eat->aettea->aetate->aet
O mapa hash só começa a ajudar depois que essa decisão esta certa.
Passo 4 — Agrupar por chave derivada
Agora o problema vira:
- calcula a chave
- pega o grupo daquela chave
- adiciona a palavra
O ponto forte da solução esta na chave, não no Map isolado.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function groupAnagrams(strs: string[]): string[][] {
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n * k log k)
Espaço: O(n * k)
Solução 1 — Procurar grupo por grupo
Correta, mas com trabalho repetido.
export function groupAnagrams(strs: string[]): string[][] {
const groups: string[][] = []
for (const word of strs) {
const normalizedWord = word.split('').sort().join('')
let placed = false
for (const group of groups) {
const normalizedGroup = group[0].split('').sort().join('')
if (normalizedGroup === normalizedWord) {
group.push(word)
placed = true
break
}
}
if (!placed) {
groups.push([word])
}
}
return groups.map((group) => [...group].sort()).sort((a, b) => a[0].localeCompare(b[0]))
}Solução 2 — Mapa hash com chave canonica
Agora cada palavra encontra seu grupo em acesso direto.
export function groupAnagrams(strs: string[]): string[][] {
const groups = new Map<string, string[]>()
for (const word of strs) {
const key = word.split('').sort().join('')
const group = groups.get(key) ?? []
group.push(word)
groups.set(key, group)
}
return [...groups.values()]
}Se quiser discutir otimização em entrevista, da para mencionar frequência de letras como chave alternativa.
A ideia continua a mesma: primeiro derivar uma representação canonica, depois guardar isso num mapa hash.
O que dizer na entrevista
Uma explicação curta e boa seria:
O ponto principal aqui e achar uma representação canonica para todos os anagramas do mesmo grupo. Eu uso a palavra ordenada como chave. Depois disso, o
mapa hashvira só o mecanismo de agrupamento: mesma chave, mesmo grupo.
Isso mostra que você:
- entendeu que a escolha da chave vem antes da estrutura
- explicou o agrupamento de forma limpa
- tratou o map como ferramenta, não como magia
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- agrupar itens equivalentes
- derivar uma chave de comparação
- fazer deduplicação por representação canonica
- separar responsabilidade entre normalizacao e armazenamento
O ponto não e decorar
groupAnagrams.
O ponto e aprender a escolher uma chave que represente o que o problema considera igual.