Duas palavras podem ser consideradas anagramas de si mesmas se as letras de uma palavra podem ser realocadas para formar a outra palavra. Dada uma string qualquer, desenvolva um algoritmo que encontre o número de pares de substrings que são anagramas
Respostas
Para encontrarmos todos os anagramas em uma palavra, é necessário encontrar todas as formas de agrupar as suas letras. Assim, ao realizarmos dois agrupamentos distintos, os anagramas terão as mesmas quantidades de letras iguais, independente da ordem em que apareçam.
Para resolvermos essa questão, devemos aprender o que é um algoritmo.
O que é um algoritmo?
Um algoritmo é uma sequência de passos que devem ser seguidos para solucionar um problema, seja em uma linguagem de programação ou na vida real.
Para encontrarmos todos os anagramas em uma palavra, é necessário encontrar todas as formas de agrupar as suas letras. Assim, ao realizarmos dois agrupamentos distintos, os anagramas terão as mesmas quantidades de letras iguais, independente da ordem em que apareçam.
Assim, o algoritmo que procura os anagramas contidos em uma palavra, em Python, é:
import string
def find_anagrams(word):
word_as_list = list(word)
tamanho = 2
offset = 1
anagramas = 0
while (tamanho <= len(word)):
deslocamento_inicial = 0
while(deslocamento_inicial + tamanho <= len(word)):
dict_letters = dict.fromkeys(string.ascii_lowercase, 0)
for letter in word_as_list[deslocamento_inicial:deslocamento_inicial+tamanho]:
dict_letters[letter] += 1
while (deslocamento_inicial + tamanho + offset +1<= len(word)):
dict_substring = dict.fromkeys(string.ascii_lowercase, 0)
for letter in word_as_list[deslocamento_inicial+1+offset:deslocamento_inicial+offset+tamanho+1]:
dict_substring[letter] += 1
if(dict_letters == dict_substring):
anagrama1 = ""
anagrama2 = ""
for letter in word_as_list[deslocamento_inicial:deslocamento_inicial+tamanho]:
anagrama1+= "".join(letter)
for letter in word_as_list[deslocamento_inicial+offset+1:deslocamento_inicial+offset+tamanho+1]:
anagrama2+= "".join(letter)
print(f"{anagramas+1}º: {anagrama1} e {anagrama2} são anagramas")
anagramas += 1
offset += 1
deslocamento_inicial += 1
offset = 0
tamanho += 1
print(f"Total: {anagramas} anagrama(s)")
if __name__ == "__main__":
while(True):
word_to_find_anagrams = input("Encontre anagramas de: ")
find_anagrams(word=word_to_find_anagrams)
Para aprender mais sobre algoritmos, acesse:
brainly.com.br/tarefa/19885120
Resposta:
import java.util.ArrayList;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class anagramas {
public static Map<String, Integer> contar(String frase)
{
Map<String, Integer> map = new TreeMap<>();
for(char item : frase.toCharArray())
{
Integer s = map.get(String.valueOf(item));
if (s != null)
{
map.put(String.valueOf(item), ++s);
}
else
{
map.put(String.valueOf(item), 1);
}
}
return map;
}
public static void Imprimir(Map<String, Integer> items) {
for (Map.Entry<String, Integer> a : items.entrySet()) {
System.out.println(a.getKey() + ": " + a.getValue());
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Digite a Palavra");
String palavra = scanner.next();
Map<String, Integer> map = contar(palavra.replace(" ", "").toLowerCase());
ArrayList<String> anagramas = new ArrayList<String>();
for(int i = 0; i <palavra.length(); i++) {
for(int j = 1; j < palavra.length(); j++) {
if(palavra.charAt(i) == palavra.charAt(j) && i !=j && i < j) {
if(palavra.charAt(i) == palavra.charAt(i+1)) {
String x = palavra.substring(i, i + 1);
anagramas.add(x);
} else {
String y = palavra.substring(i, j);
String z = palavra.substring(i + 1, j + 1);
String h = palavra.substring(i, i + 1);
anagramas.add(h);
anagramas.add(y);
anagramas.add(z);
}
}
}
}
Imprimir(map);
System.out.println(anagramas);
}
}
Explicação passo a passo: