Escreva um programa que lê duas palavras do teclado e verifica se elas formam um anagrama. Duas ou mais palavras formam um anagrama quando todas as letras de uma palavra ocorrem em mesmo número (independente da posição) em outra palavra. As palavras roma, mora, oram, amor e ramo, por exemplo, formam anagramas.
Passo 1
O enunciado pede um programa que leia duas palavras do teclado e verifique se elas formam um anagrama. Mais precisamente:
- Entrada: duas palavras (cada uma digitada pelo usuário).
- Saída: uma indicação verdadeira/falsa (ou uma mensagem) dizendo se as duas palavras são anagramas.
Informações e decisões que vou assumir (sem te perguntar nada): - Vou tratar a verificação como insensível a maiúsculas/minúsculas (isto é,
Romaeamorsão anagramas). - Vou assumir que cada “palavra” é uma sequência de letras sem espaços internos. Vou remover espaços no início/fim com
strip(). - Exemplo: as palavras
romaeamordevem ser consideradas anagramas.
Passo 2
Entender o que significa ser anagrama de forma operacional:
Duas palavras são anagramas quando cada letra aparece o mesmo número de vezes nas duas palavras, independentemente da ordem. Então, para cada letra :
Duas palavras são anagramas quando cada letra aparece o mesmo número de vezes nas duas palavras, independentemente da ordem. Então, para cada letra
- o número de ocorrências de
em palavra A tem que ser igual ao número de ocorrências de em palavra B.
Isso sugere duas ideias óbvias de algoritmo:
- Ordenar as letras de cada palavra e comparar as palavras ordenadas. Se forem iguais, são anagramas.
- Contar a frequência de cada letra em cada palavra e comparar as frequências.
Passo 3
Comparação das duas ideias (prós e contras):
- Ordenação: implementar é simples (em Python basta
sorted()), e a verificação reduz a comparar duas sequências. Complexidade de tempo:, onde é o comprimento das palavras (assumindo tamanhos parecidos). - Contagem de frequências: é possível em uma única passagem por cada palavra, usando um dicionário (ou um vetor de contagem para alfabetos fixos). Complexidade de tempo:
e espaço extra também em função do número distinto de letras.
Vou escolher a abordagem por contagem de frequências porque é eficiente (
) e didaticamente mostra diretamente a ideia “mesmo número de cada letra”. Além disso, é fácil de implementar sem usar funções que “escondem” a lógica (como
sorted()), o que ajuda na hora da prova.Passo 4
Descrever o algoritmo escolhido passo a passo (sem código ainda), de forma que dê pra escrever na prova:
- Ler a palavra 1 e a palavra 2 do teclado.
- Normalizar: aplicar
lower()para ignorar diferença maiúsc./minúsc. Remover espaços laterais comstrip(). - Se os comprimentos das palavras forem diferentes, então NÃO são anagramas (porque não é possível ter as mesmas quantidades de letra).
- Criar um dicionário
freqvazio para contar letras da palavra 1. - Percorrer cada letra
cda palavra 1 e fazerfreq[c] = freq.get(c, 0) + 1. - Percorrer cada letra
cda palavra 2: para cadac:- Se
cnão estiver emfreq, então NÃO são anagramas. - Caso contrário, diminuir
freq[c]em 1. - Se
freq[c]ficar zero, remover a chavecdo dicionário (opcional, mas útil).
- Se
- No final: se
freqestiver vazio (todas as contagens zeraram), então são anagramas; caso contrário, não são.
Observação: esse processo compara as frequências “no mesmo sentido” e usa apenas duas passagens (uma por palavra), logo tempo linear em.
Passo 5
Por que a verificação de comprimento serve como filtro rápido?
- Se duas palavras têm comprimentos diferentes, existe pelo menos uma letra a mais em uma delas, logo as contagens não podem coincidir. Isso evita contagens desnecessárias.
- Em termos de eficiência, evita fazer passes adicionais quando já é impossível.
Passo 6
Exemplo concreto (traçar o algoritmo passo a passo) com
roma e amor:- Normalizar:
roma,amor(já em minúsculas). - Comprimento: ambos têm
letras, ok. - Construir
freqa partir deroma:r:freq = {'r':1}o:freq = {'r':1, 'o':1}m:freq = {'r':1, 'o':1, 'm':1}a:freq = {'r':1, 'o':1, 'm':1, 'a':1}
- Percorrer
amore diminuir:a: existe, decrementaapara 0 → remove'a'.m: existe, decrementampara 0 → remove'm'.o: existe, decrementaopara 0 → remove'o'.r: existe, decrementarpara 0 → remove'r'.
- No final
freqé vazio → são anagramas.
Passo 7
Tratamento de casos especiais que podem aparecer na prova:
- Letras repetidas (ex.:
aabvsaba): o método por contagem funciona normalmente. - Mesmo caractere com caixa diferente (ex.:
Romavsamor): normalização comlower()resolve. - Caracteres não-alfabéticos (se o enunciado não mencionar): é preciso decidir se devem ser considerados. Neste programa vou considerar qualquer caractere presente na palavra (ou seja, se houver hífen ou acento, eles também entram na contagem). Se na prova exigir ignorar espaços/pontuação, deve-se remover esses caracteres antes de contar.
Passo 8
Complexidade e memória:
- Tempo: duas passagens pelas palavras →
, onde é o comprimento da palavra (assumindo que são de tamanhos parecidos). - Memória: dicionário com no máximo tantos pares quanto caracteres distintos (no pior caso, proporcional a
). Em geral com distinto de caracteres.
Passo 9
Pseudocódigo resumido (ajuda para escrever o programa rápido na prova):
- Ler
w1,w2 w1 = w1.strip().lower()w2 = w2.strip().lower()- Se
len(w1) != len(w2): imprimir “não são anagramas” e sair freq = {}- Para cada
cemw1:freq[c] = freq.get(c, 0) + 1 - Para cada
cemw2:- Se
cnão emfreq: imprimir “não são anagramas” e sair freq[c] -= 1- Se
freq[c] == 0: removercdefreq
- Se
- Se
freqvazio: imprimir “são anagramas” senão imprimir “não são anagramas”
Resposta
# Programa em Python que lê duas palavras e verifica se são anagramas
def sao_anagramas(w1, w2):
# Normalização: remover espaços laterais e ignorar maiúsc./minúsc.
a = w1.strip().lower()
b = w2.strip().lower()
# Filtro rápido pelo comprimento
if len(a) != len(b):
return False
# Contagem de frequências da primeira palavra
freq = {}
for ch in a:
freq[ch] = freq.get(ch, 0) + 1
# Subtrai as frequências com a segunda palavra
for ch in b:
if ch not in freq:
return False
freq[ch] -= 1
if freq[ch] == 0:
del freq[ch]
# Se todas as contagens zeraram, são anagramas
return len(freq) == 0
# Leitura das duas palavras (uma por linha)
palavra1 = input()
palavra2 = input()
if sao_anagramas(palavra1, palavra2):
print("As palavras são anagramas.")
else:
print("As palavras não são anagramas.")