Dadas dos arrays arr1[] y arr2[] que consisten en strings, la tarea es imprimir el recuento de anagramas de cada string en arr2[] que están presentes en arr1[].
Ejemplos:
Entrada: arr1[] = [“geeks”, “aprender”, “para”, “egeks”, “ealrn”], arr2[] = [“kgees”, “rof”, “nrael”]
Salida: 2 1 2
Explicación:
Anagramas de arr2[0] (“kgees”) en arr1 : “geeks” y “egeks”.
Anagramas de arr2[1] (“rof”) en arr1 : “para”.
Anagramas de arr2[2] (“nrael”) en arr1 : “aprender” y “ealrn”.Entrada: arr1[] = [“code”, “to”, “grow”, “odce”], arr2[] = [“edoc”, “wgor”, “ot”]
Salida: 2 1 1
Explicación:
Anagramas de arr2[0] (“edoc”) en arr1 “código” y “odce”.
Anagramas de arr2[1] (“wgor”) en arr1 “crecer”.
Anagramas de arr2[2] (“ot”) en arr1 “to”
Enfoque:
Para resolver el problema, la idea es utilizar el conteo de frecuencias con la ayuda de HashMap . Almacene las frecuencias de cada string en arr1[] en hashmap en su forma ordenada. Atraviese arr2[], ordene strings en arr2[] e imprima sus respectivas frecuencias en HashMap.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to count the
// number of anagrams of
// each string in a given
// array present in
// another array
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// count of anagrams
void count(string arr1[],
string arr2[],
int n, int m)
{
// Store the frequencies
// of strings in arr1[]
unordered_map<string, int> freq;
for (int i = 0; i < n; i++) {
// Sort the string
sort(arr1[i].begin(),
arr1[i].end());
// Increase its frequency
// in the map
freq[arr1[i]]++;
}
for (int i = 0; i < m; i++) {
// Sort the string
sort(arr2[i].begin(),
arr2[i].end());
// Display its anagrams
// in arr1[]
cout << freq[arr2[i]]
<< " ";
}
}
// Driver Code
int main()
{
string arr1[] = { "geeks", "learn",
"for", "egeks",
"ealrn" };
int n = sizeof(arr1)
/ sizeof(string);
string arr2[] = { "kgees", "rof",
"nrael" };
int m = sizeof(arr2)
/ sizeof(string);
count(arr1, arr2, n, m);
}
Java
// Java program to count the number
// of anagrams of each String in a
// given array present in
// another array
import java.util.*;
class GFG{
static String sortString(String inputString)
{
// Convert input string to char array
char tempArray[] = inputString.toCharArray();
// Sort tempArray
Arrays.sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Function to return the
// count of anagrams
static void count(String arr1[],
String arr2[],
int n, int m)
{
// Store the frequencies
// of Strings in arr1[]
HashMap<String, Integer> freq = new HashMap<>();
for(int i = 0; i < n; i++)
{
// Sort the String
arr1[i] = sortString(arr1[i]);
// Increase its frequency
// in the map
if (freq.containsKey(arr1[i]))
{
freq.put(arr1[i],
freq.get(arr1[i]) + 1);
}
else
{
freq.put(arr1[i], 1);
}
}
for(int i = 0; i < m; i++)
{
// Sort the String
arr2[i] = sortString(arr2[i]);
// Display its anagrams
// in arr1[]
System.out.print(freq.get(arr2[i]) + " ");
}
}
// Driver Code
public static void main(String[] args)
{
String arr1[] = { "geeks", "learn",
"for", "egeks",
"ealrn" };
int n = arr1.length;
String arr2[] = { "kgees", "rof",
"nrael" };
int m = arr2.length;
count(arr1, arr2, n, m);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to count the number
# of anagrams of each string in a
# given array present in another array
# Function to return the count of anagrams
def count(arr1, arr2, n, m):
# Store the frequencies of
# strings in arr1
freq = {}
for word in arr1:
# Sort the string
word = ' '.join(sorted(word))
# Increase its frequency
if word in freq.keys():
freq[word] = freq[word] + 1
else:
freq[word] = 1
for word in arr2:
# Sort the string
word = ' '.join(sorted(word))
# Display its anagrams
# in arr1
if word in freq.keys():
print(freq[word], end = " ")
else:
print(0, end = " ")
print()
# Driver Code
if __name__ == '__main__':
arr1 = [ "geeks", "learn", "for",
"egeks", "ealrn" ]
n = len(arr1)
arr2 = [ "kgees", "rof", "nrael" ]
m = len(arr2)
count(arr1, arr2, n, m)
# This code is contributed by Pawan_29
C#
// C# program to count the number
// of anagrams of each String in a
// given array present in
// another array
using System;
using System.Collections.Generic;
class GFG{
static String sortString(String inputString)
{
// Convert input string to char array
char []tempArray = inputString.ToCharArray();
// Sort tempArray
Array.Sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Function to return the
// count of anagrams
static void count(String []arr1,
String []arr2,
int n, int m)
{
// Store the frequencies
// of Strings in arr1[]
Dictionary<String,
int> freq = new Dictionary<String,
int>();
for(int i = 0; i < n; i++)
{
// Sort the String
arr1[i] = sortString(arr1[i]);
// Increase its frequency
// in the map
if (freq.ContainsKey(arr1[i]))
{
freq[arr1[i]] =
freq[arr1[i]] + 1;
}
else
{
freq.Add(arr1[i], 1);
}
}
for(int i = 0; i < m; i++)
{
// Sort the String
arr2[i] = sortString(arr2[i]);
// Display its anagrams
// in arr1[]
Console.Write(freq[arr2[i]] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
String []arr1 = { "geeks", "learn",
"for", "egeks",
"ealrn" };
int n = arr1.Length;
String []arr2 = { "kgees", "rof",
"nrael" };
int m = arr2.Length;
count(arr1, arr2, n, m);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to count the number
// of anagrams of each String in a
// given array present in
// another array
function sortString(inputString)
{
// Convert input string to char array
let tempArray = inputString.split('');
// Sort tempArray
tempArray.sort();
// Return new sorted string
return tempArray.join("");
}
// Function to return the
// count of anagrams
function count(arr1, arr2, n, m)
{
// Store the frequencies
// of Strings in arr1[]
let freq = new Map();
for(let i = 0; i < n; i++)
{
// Sort the String
arr1[i] = sortString(arr1[i]);
// Increase its frequency
// in the map
if (freq.has(arr1[i]))
{
freq.set(arr1[i],
freq.get(arr1[i]) + 1);
}
else
{
freq.set(arr1[i], 1);
}
}
for(let i = 0; i < m; i++)
{
// Sort the String
arr2[i] = sortString(arr2[i]);
// Display its anagrams
// in arr1[]
document.write(freq.get(arr2[i]) + " ");
}
}
// Driver code
let arr1 = [ "geeks", "learn",
"for", "egeks",
"ealrn" ];
let n = arr1.length;
let arr2 = [ "kgees", "rof",
"nrael" ];
let m = arr2.length;
count(arr1, arr2, n, m);
// This code is contributed by souravghosh0416.
</script>
2 1 2
Complejidad de tiempo: O(n*plog(p)+m*qlog(q)) donde n y m son los tamaños de la array y p y q son el tamaño máximo de la string presente en arr1 y arr2 respectivamente.
Espacio auxiliar: O(n+m).
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por arjun_rajput y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA