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 é, Roma e amor sã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 roma e amor devem 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 c:
  • o número de ocorrências de c em palavra A tem que ser igual ao número de ocorrências de c em palavra B.
Isso sugere duas ideias óbvias de algoritmo:
  1. Ordenar as letras de cada palavra e comparar as palavras ordenadas. Se forem iguais, são anagramas.
  2. 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: \mathcal{O}(n \log n), onde n é 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: \mathcal{O}(n) 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 ( \mathcal{O}(n)) 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:
  1. Ler a palavra 1 e a palavra 2 do teclado.
  2. Normalizar: aplicar lower() para ignorar diferença maiúsc./minúsc. Remover espaços laterais com strip().
  3. 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).
  4. Criar um dicionário freq vazio para contar letras da palavra 1.
  5. Percorrer cada letra c da palavra 1 e fazer freq[c] = freq.get(c, 0) + 1.
  6. Percorrer cada letra c da palavra 2: para cada c:
    • Se c não estiver em freq, então NÃO são anagramas.
    • Caso contrário, diminuir freq[c] em 1.
    • Se freq[c] ficar zero, remover a chave c do dicionário (opcional, mas útil).
  7. No final: se freq estiver 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 n.

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 4 letras, ok.
  • Construir freq a partir de roma:
    • 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 amor e diminuir:
    • a: existe, decrementa a para 0 → remove 'a'.
    • m: existe, decrementa m para 0 → remove 'm'.
    • o: existe, decrementa o para 0 → remove 'o'.
    • r: existe, decrementa r para 0 → remove 'r'.
  • No final freq é vazio → são anagramas.

Passo 7

Tratamento de casos especiais que podem aparecer na prova:
  • Letras repetidas (ex.: aab vs aba): o método por contagem funciona normalmente.
  • Mesmo caractere com caixa diferente (ex.: Roma vs amor): normalização com lower() 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 → \mathcal{O}(n), onde n é 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 n). Em geral \mathcal{O}(k) com k 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 c em w1: freq[c] = freq.get(c, 0) + 1
  • Para cada c em w2:
    • Se c não em freq: imprimir “não são anagramas” e sair
    • freq[c] -= 1
    • Se freq[c] == 0: remover c de freq
  • Se freq vazio: 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.")

Exercícios relacionados