Classify strings from an array using Custom Hash Function

0 0 6 minutes read

Given an array of strings arr[] consisting of N strings, the task is to categorize the strings according to the hash value obtained by adding ASCII values % 26 of the characters in the string.

Examples:

Input: arr[][] = {“zambiatek”, “for”, “zambiatek”}
Output:
zambiatek zambiatek
for
Explanation:
The hash value of string “for” is (102 + 111 + 114) % 26 = 14
The hash value of string “zambiatek” is (103 + 101 + 101 + 107 + 115) % 26 = 7
Therefore, two “zambiatek” are grouped together and “for” is kept in another group.

Input: arr[][] = {“adf”, “aahe”, “bce”, “bgdb”}
Output:
aahe bgdb
bce
adf
Explanation:
The hash value of string “adf” is (97 + 100 + 102)%26 = 13
The hash value of string “aahe” is (97 + 97 + 104 + 101)%26 = 9
The hash value of string “bce” is (98 + 99 + 101)%26 = 12
The hash value of string “bgdb” is (98 + 103 + 100 + 98)%26 = 9
Therefore, strings “aahe” and “bgdb” have same hashed value, so they are grouped together.

Approach: The idea is to use Map Data Structure for grouping together the strings with the same hash values. Follow the steps below to solve the problem:

Initialize a Map, say mp, to map hash values with respective strings in a vector.
Traverse the given array of strings and perform the following steps:
- Calculate the hash value of the current string according to the given function.
- Push the string into the vector with the calculated hash values of the string as key in the map mp.
Finally, traverse the map mp and print all the strings of respective keys.

Below is the implementation of the above approach:

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>

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApp1
{
    class Program
    {
        // 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 CategorisationOfStrings(List<string> s,
                                            int N)
        {
            // Maps strings with their strings
            // respective hash values
            SortedDictionary<int, List<string>> mp = new SortedDictionary<int, List<string>>();
 
            // 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
                if (mp.ContainsKey(temp))
                {
                    mp[temp].Add(s[i]);
                }
                else
                {
                    mp[temp] = new List<string>();
                    mp[temp].Add(s[i]);
                }
            }
 
            // Traverse over the map mp
            foreach (var entry in mp)
            {
                // Print the result
                foreach (string str in entry.Value)
                {
                    Console.Write(str + " ");
                }
                Console.WriteLine();
            }
        }
 
        static void Main(string[] args)
        {
            string[] Sarr = { "adf", "aahe", "bce", "bgdb" };
            List<string> arr = new List<string>(Sarr);
            int N = arr.Count;
 
            CategorisationOfStrings(arr, N);
        }
    }
}

Output

aahe bgdb 
bce 
adf

Time Complexity: O(N*M), where M is the length of the longest string.
Auxiliary Space: O(N*M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!