Dada una string S en forma de oración, la tarea es encontrar la palabra del texto con el número máximo de sus anagramas presentes en la oración dada.
Ejemplo:
Entrada: S = «por favor, guarda silencio y escucha lo que dice el profesor»
Salida: silencio
Explicación:
Solo la palabra » silencio » tiene un anagrama ( escuchar ) presente en la oración.Entrada: S = «gato no es un perro y la espada no tiene palabras cuando el gobierno crea acto entonces qué es tac»
Salida: gato
Explicación:
La palabra » gato » tiene dos anagramas («acto», «tac») presentes en la oración .
La palabra » palabras » tiene un anagrama («espada») presente en la oración.
De ahí que la palabra con el máximo de anagramas sea “gato” .
Enfoque:
Es necesario hacer las siguientes observaciones para resolver el programa:
Propiedad de los Números Primos : El producto de cualquier combinación de números primos genera un número único que no puede ser obtenido por ninguna otra combinación de números primos.
Siga los pasos a continuación para resolver el problema:
- Asigne a cada alfabeto un número primo distinto .
- Para cada palabra en la string dada, calcule el producto de los números primos asignados a los caracteres de esa palabra y guárdelo en un HashMap .
- Calcula el producto de los números primos asignados a los caracteres de una palabra y guárdalo en un HashMap .
- Encuentre el producto con la máxima frecuencia en el HashMap e imprima uno de los anagramas correspondientes como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ Program to find the word
// with most anagrams in a sentence
#include <bits/stdc++.h>
using namespace std;
// Function to find the word with
// maximum number of anagrams
string largestAnagramGrp(vector<string> arr)
{
// Primes assigned to 26 alphabets
int prime[] = {2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101};
int max = -1;
long maxpdt = -1;
// Stores the product and
// word mappings
unordered_map<long long, string> W;
// Stores the frequencies
// of products
unordered_map<long long, long> P;
for (string temp : arr)
{
long pdt = 1;
// Calculate the product of
// primes assigned
for (char t : temp)
{
pdt *= prime[t - 'a'];
}
// If product already exists
if (P.find(pdt) != P.end())
{
P[pdt]++;
}
// Otherwise
else
{
W[pdt] = temp;
P[pdt] = 1;
}
}
// Fetch the most frequent product
for (auto e : P)
{
if (max < e.second)
{
max = e.second;
maxpdt = e.first;
}
}
// Return a string
// with that product
return W[maxpdt];
}
// Driver Code
int main()
{
char S[] = "please be silent and listen to what the professor says ";
vector<string> arr;
char *token = strtok(S, " ");
while (token != NULL)
{
arr.push_back(token);
token = strtok(NULL, " ");
}
cout << largestAnagramGrp(arr) << endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java Program to find the word
// with most anagrams in a sentence
import java.util.*;
class GFG {
// Function to find the word with
// maximum number of anagrams
private static String largestAnagramGrp(
String arr[])
{
// Primes assigned to 26 alphabets
int prime[]
= { 2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101 };
int max = -1;
long maxpdt = -1;
// Stores the product and
// word mappings
HashMap<Long, String> W
= new HashMap<>();
// Stores the frequencies
// of products
HashMap<Long, Integer> P
= new HashMap<>();
for (String temp : arr) {
char c[] = temp.toCharArray();
long pdt = 1;
// Calculate the product of
// primes assigned
for (char t : c) {
pdt *= prime[t - 'a'];
}
// If product already exists
if (P.containsKey(pdt)) {
P.put(pdt, P.get(pdt) + 1);
}
// Otherwise
else {
W.put(pdt, temp);
P.put(pdt, 1);
}
}
// Fetch the most frequent product
for (Map.Entry<Long, Integer>
e : P.entrySet()) {
if (max < e.getValue()) {
max = e.getValue();
maxpdt = e.getKey();
}
}
// Return a string
// with that product
return W.get(maxpdt);
}
// Driver Code
public static void main(String args[])
{
String S = "please be silent and listen"
+ " to what the professor says ";
String arr[] = S.split("[ ]+");
System.out.println(largestAnagramGrp(arr));
}
}
Python3
# Python3 Program to find the word
# with most anagrams in a sentence
# Function to find the word with
# maximum number of anagrams
def largestAnagramGrp(arr):
# Primes assigned to 26 alphabets
prime= [2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101]
max = -1
maxpdt = -1
# Stores the product and
# word mappings
W = {}
# Stores the frequencies
# of products
P = {}
for temp in arr:
c = [i for i in temp]
pdt = 1
# Calculate the product of
# primes assigned
for t in c:
pdt *= prime[ord(t) - ord('a')]
# If product already exists
if (pdt in P):
P[pdt] = P.get(pdt, 0) + 1
# Otherwise
else:
W[pdt] = temp
P[pdt] = 1
# Fetch the most frequent product
for e in P:
if (max < P[e]):
max = P[e]
maxpdt = e
# Return a string
# with that product
return W[maxpdt]
# Driver Code
if __name__ == '__main__':
S = "please be silent and listen to what the professor says"
arr = S.split(" ")
print(largestAnagramGrp(arr))
# This code is contributed by mohit kumar 29
C#
// C# program to find the word
// with most anagrams in a sentence
using System;
using System.Collections.Generic;
class GFG{
// Function to find the word with
// maximum number of anagrams
private static String largestAnagramGrp(String []arr)
{
// Primes assigned to 26 alphabets
int []prime = { 2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101 };
int max = -1;
long maxpdt = -1;
// Stores the product and
// word mappings
Dictionary<long,
String> W = new Dictionary<long,
String>();
// Stores the frequencies
// of products
Dictionary<long,
int> P = new Dictionary<long,
int>();
foreach(String temp in arr)
{
char []c = temp.ToCharArray();
long pdt = 1;
// Calculate the product of
// primes assigned
foreach(char t in c)
{
pdt *= prime[t - 'a'];
}
// If product already exists
if (P.ContainsKey(pdt))
{
P[pdt] = P[pdt] + 1;
}
// Otherwise
else
{
W.Add(pdt, temp);
P.Add(pdt, 1);
}
}
// Fetch the most frequent product
foreach(KeyValuePair<long, int> e in P)
{
if (max < e.Value)
{
max = e.Value;
maxpdt = e.Key;
}
}
// Return a string
// with that product
return W[maxpdt];
}
// Driver Code
public static void Main(String []args)
{
String S = "please be silent and listen" +
" to what the professor says ";
String []arr = S.Split(' ');
Console.WriteLine(largestAnagramGrp(arr));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// JavaScript program to find the word
// with most anagrams in a sentence
// Function to find the word with
// maximum number of anagrams
function largestAnagramGrp(arr)
{
// Primes assigned to 26 alphabets
var prime = [ 2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, ];
var max = -1;
var maxpdt = -1;
// Stores the product and
// word mappings
var W = {};
// Stores the frequencies
// of products
var P = {};
for (const temp of arr)
{
var c = temp.split("");
var pdt = 1;
// Calculate the product of
// primes assigned
for(const t of c)
{
pdt *= prime[t.charCodeAt(0) -
"a".charCodeAt(0)];
}
// If product already exists
if (P.hasOwnProperty(pdt))
{
P[pdt] = P[pdt] + 1;
}
// Otherwise
else
{
W[pdt] = temp;
P[pdt] = 1;
}
}
// Fetch the most frequent product
for (const [key, value] of Object.entries(P))
{
if (max < value)
{
max = value;
maxpdt = key;
}
}
// Return a string
// with that product
return W[maxpdt];
}
// Driver Code
var S = "please be silent and listen" +
" to what the professor says ";
var arr = S.split(" ");
document.write(largestAnagramGrp(arr));
// This code is contributed by rdtank
</script>
Producción:
silent
Complejidad de tiempo: O(N), N es la longitud de la string excluyendo los espacios en blanco.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por debarpan_bose_chowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA