24 de Março
Anagrama válido
Como perceber que anagrama e sobre frequência, não sobre ordem, e justificar a troca da ordenação por contagem.
Strings e Contagem de Frequência Iniciante 12 min TypeScript
Dadas duas strings s e t, retorne true se t for um anagrama de s e false caso contrario.
Um anagrama usa as mesmas letras com a mesma quantidade, mas em ordem diferente.
Exemplo:
Input: s = "anagram", t = "nagaram"
Output: true
O que perceber antes de codar
- Ordem não importa. Quantidade de cada caractere importa.
- Se os comprimentos forem diferentes, a resposta já e `false`.
- O problema não pede para montar o anagrama. Só pede validar.
Erros comuns
- comparar apenas o conjunto de letras e esquecer a quantidade
- usar ordenação sem conseguir explicar por que isso funciona
Passo 1 — Entender o que define um anagrama
Muita gente olha para esse problema e pensa em ordem.
Mas ordem não e o ponto.
Se listen e silent sao anagramas, não e porque as letras estao em lugares parecidos. E porque cada letra aparece a mesma quantidade de vezes nos dois lados.
Passo 2 — Escrever a primeira versão correta
Uma forma simples de resolver e ordenar as duas strings e comparar:
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false
}
const sortedS = s.split('').sort().join('')
const sortedT = t.split('').sort().join('')
return sortedS === sortedT
}
Funciona porque a ordenação agrupa os mesmos caracteres na mesma ordem.
Passo 3 — Entender o que a ordenação esta revelando
Ordenar não e magia.
Ele só torna fácil enxergar uma coisa:
a frequência de cada caractere precisa bater.
Se esse e o critério real, você pode trabalhar diretamente com frequência.
Passo 4 — Contar em vez de ordenar
Use um mapa hash para contar os caracteres de s.
Depois percorra t:
- se um caractere não existir no
Map, falha - se a contagem ficar negativa, falha
- se tudo zerar direito, e anagrama
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function isAnagram(s: string, t: string): boolean {
// sua solução aqui
return false
}
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)
Espaço: O(n)
Solução 1 — Ordenar e comparar O(n log n)
Essa e a versão inicial mais comum.
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false
}
const sortedS = s.split('').sort().join('')
const sortedT = t.split('').sort().join('')
return sortedS === sortedT
}Boa para começar. Mas a parte cara aqui e a ordenação.
Solução 2 — Contagem de frequência com mapa hash em O(n)
Se anagrama depende de quantidade, conte quantidade.
export function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) {
return false
}
const counts = new Map<string, number>()
for (const char of s) {
counts.set(char, (counts.get(char) ?? 0) + 1)
}
for (const char of t) {
const nextCount = (counts.get(char) ?? 0) - 1
if (nextCount < 0) {
return false
}
counts.set(char, nextCount)
}
return true
}Você não precisa reordenar nada. Só precisa garantir que cada letra entrou e saiu a mesma quantidade de vezes.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão mais simples ordena as duas strings e compara, o que custa
O(n log n). Como anagrama depende de frequência e não de ordem, eu posso contar caracteres commapa hashe verificar tudo emO(n).
Isso mostra que você:
- sabe explicar por que a versão inicial funciona
- identificou o critério real do problema
- trocou a ferramenta sem perder o fio da explicação
Quando esse padrão aparece de novo
Esse padrão reaparece quando o problema pede:
- contar ocorrencias
- comparar distribuição de caracteres
- validar se duas entradas tem a mesma composição
- manter frequência durante uma janela
O ponto não e decorar “anagrama = hash map”.
O ponto e perceber quando o problema e de contagem, mesmo que o enunciado fale de strings.