Dada una array de strings arr[] que consta de N strings, la tarea es categorizar las strings de acuerdo con el valor hash obtenido al agregar los valores ASCII % 26 de los caracteres de la string.
Ejemplos:
Entrada: arr[][] = {“geeks”, “for”, “geeks”}
Salida:
geeks geeks
for
Explicación:
El valor hash de la string “for” es (102 + 111 + 114) % 26 = 14
El hash el valor de la string «geeks» es (103 + 101 + 101 + 107 + 115) % 26 = 7
Por lo tanto, dos «geeks» se agrupan y «for» se mantiene en otro grupo.Entrada: arr[][] = {“adf”, “aahe”, “bce”, “bgdb”}
Salida:
aahe bgdb bce
adf
Explicación
:
El valor hash de la string “adf” es (97 + 100 + 102)% 26 = 13
El valor hash de la string «aahe» es (97 + 97 + 104 + 101)% 26 = 9
El valor hash de la string «bce» es (98 + 99 + 101)% 26 = 12
El valor hash de la string «bgdb» es (98 + 103 + 100 + 98)% 26 = 9
Por lo tanto, las strings «aahe» y «bgdb» tienen el mismo valor hash, por lo que se agrupan.
Enfoque: la idea es utilizar la estructura de datos del mapa para agrupar las strings con los mismos valores hash. Siga los pasos a continuación para resolver el problema:
- Inicialice un Map , digamos mp , para mapear valores hash con strings respectivas en un vector .
- Recorra la array de strings dada y realice los siguientes pasos:
- Calcule el valor hash de la string actual de acuerdo con la función dada.
- Inserte la string en el vector con los valores hash calculados de la string como clave en el mapa mp.
- Finalmente, recorra el mapa mp e imprima todas las strings de claves respectivas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the hash
// value of the string s
int stringPower(string s)
{
// Stores hash value of string
int power = 0;
int n = s.length();
// Iterate over characters of the string
for (int i = 0; i < n; i++) {
// Calculate hash value
power = (power + (s[i])) % 26;
}
// Return the hash value
return power;
}
// Function to classify the strings
// according to the given condition
void categorisation_Of_strings(
vector<string> s, int N)
{
// Maps strings with their strings
// respective hash values
map<int, vector<string> > mp;
// Traverse the array of strings
for (int i = 0; i < N; i++) {
// Find the hash value of the
// of the current string
int temp = stringPower(s[i]);
// Push the current string in
// value vector of temp key
mp[temp].push_back(s[i]);
}
// Traverse over the map mp
for (auto power : mp) {
// Print the result
for (auto str : power.second) {
cout << str << " ";
}
cout << endl;
}
}
// Driver Code
int main()
{
vector<string> arr{ "adf", "aahe",
"bce", "bgdb" };
int N = arr.size();
categorisation_Of_strings(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Vector;
class GFG{
// Function to find the hash
// value of the string s
static int stringPower(String s)
{
// Stores hash value of string
int power = 0;
int n = s.length();
char C[] = s.toCharArray();
// Iterate over characters of the string
for(int i = 0; i < n; i++)
{
// Calculate hash value
power = (power + (C[i])) % 26;
}
// Return the hash value
return power;
}
// Function to classify the strings
// according to the given condition
static void categorisation_Of_strings(Vector<String> s,
int N)
{
// Maps strings with their strings
// respective hash values
Map<Integer, Vector<String> > mp = new HashMap<>();
// Traverse the array of strings
for(int i = 0; i < N; i++)
{
// Find the hash value of the
// of the current string
int temp = stringPower(s.get(i));
// Push the current string in
// value vector of temp key
if (mp.containsKey(temp))
{
mp.get(temp).add(s.get(i));
}
else
{
mp.put(temp, new Vector<String>());
mp.get(temp).add(s.get(i));
}
}
// Traverse over the map mp
for(Map.Entry<Integer,
Vector<String>> entry : mp.entrySet())
{
// Print the result
for(String str : entry.getValue())
{
System.out.print(str + " ");
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
String[] Sarr = { "adf", "aahe", "bce", "bgdb" };
Vector<String> arr = new Vector<String>(
Arrays.asList(Sarr));
int N = arr.size();
categorisation_Of_strings(arr, N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach
# Function to find the hash
# value of the string s
def stringPower(s):
# Stores hash value of string
power = 0
n = len(s)
# Iterate over characters of the string
for i in range(n):
# Calculate hash value
power = (power + ord(s[i])) % 26
# Return the hash value
return power
# Function to classify the strings
# according to the given condition
def categorisation_Of_strings(s, N):
# Maps strings with their strings
# respective hash values
mp = {}
# Traverse the array of strings
for i in range(N):
# Find the hash value of the
# of the current string
temp = stringPower(s[i])
# Push the current string in
# value vector of temp key
if temp in mp:
mp[temp].append(s[i])
else:
mp[temp] = []
mp[temp].append(s[i])
# Traverse over the map mp
for i in sorted (mp) :
# Print the result
for str in mp[i]:
print(str,end = " ")
print("\n",end = "")
# Driver Code
if __name__ == '__main__':
arr = ["adf", "aahe", "bce", "bgdb"]
N = len(arr)
categorisation_Of_strings(arr, N)
# This code is contributed by ipg2016107.
Javascript
<script>
// Javascript program for the above approach
// Function to find the hash
// value of the string s
function stringPower(s)
{
// Stores hash value of string
var power = 0;
var n = s.length;
// Iterate over characters of the string
for(var i = 0; i < n; i++)
{
// Calculate hash value
power = (power + (s[i].charCodeAt(0))) % 26;
}
// Return the hash value
return power;
}
// Function to classify the strings
// according to the given condition
function categorisation_Of_strings(s, N)
{
// Maps strings with their strings
// respective hash values
var mp = new Map();
// Traverse the array of strings
for(var i = 0; i < N; i++)
{
// Find the hash value of the
// of the current string
var temp = stringPower(s[i]);
// Push the current string in
// value vector of temp key
if (!mp.has(temp))
{
mp.set(temp, new Array());
}
var tmp = mp.get(temp);
tmp.push(s[i]);
mp.set(temp, tmp);
}
var tmp = Array();
// Traverse over the map mp
mp.forEach((value, key) => {
tmp.push(key);
});
tmp.sort((a, b) => a - b);
// Traverse over the map mp
tmp.forEach((value) => {
// Print the result
mp.get(value).forEach(element => {
document.write(element + " ");
});
document.write("<br>");
});
}
// Driver Code
var arr = [ "adf", "aahe", "bce", "bgdb" ];
var N = arr.length;
categorisation_Of_strings(arr, N);
// This code is contributed by rutvik_56
</script>
aahe bgdb bce adf
Complejidad de tiempo: O(N*M), donde M es la longitud de la string más larga.
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por deepika_sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA