2
\$\begingroup\$

problem statement

Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

[

["ate", "eat","tea"],

["nat","tan"],

["bat"]

]

Note: All inputs will be in lower-case.

My introduction of algorithm

Understand Hash collision

I came cross the question on this site, and then I started to practice on this algorithm, and gave my code review on timeout issue. One thing I like to emphasis this practice is to design a very good hash function and like to have some discussion as well. Best way to learn is to try to answer people's question, I did try to explain hash collision for a computer programmer using birthday for example, if there are 400 people then there must be at least 2 people has same birthday since there is at most 366 days in a year. You can look up birthday attack if you are interested in advanced topics.

Hash function design concerns

Related to every group of anagrams with lower case alphabetic numbers, any string in the group should be sorted to the same string. How to design your own hash function as a computer programmer? Is it fun to design a good one in algorithm problem solving? There are so many ways to design the hash function, and I just love the freedom of design in algorithm problem solving. You do not want to have hash collisions, in other words, your task is to avoid that different group of anagrams hash to the same thing.

Freedom of design

For example, work on the simple string "abc", the first intuitive idea is to concatenate a string using 01-11-21, first char 0 of substring 01 represents for 'a', second char 1 of "01" expresses only 1 of 'a'. In maximum, there are 26 alphabetic number, I choose to use '-' to separate each char's hashing result.

Further simplify the hash function, I omit the number to represent the char of alphabetic number, since counting delimiter char '-' can help to identify the alphabetic number in the string "abcdefghijklmnopqrstuvwxyz".

In the end, "abc" will be hashed to a key "1-1-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0". I like to reserve at least two chars for each alphabetic number.

Test cases

One test case is added to verify hash function key string.

Timeout concern in the design

The idea to avoid timeout issue is to generate a key for each anagram group using O(N) time complexity, instead of naive one by sorting the string, N is the string's length. To take advantage of alphabetic number only has constant of size 26, go through the string once, one char a time, to record the number of occurrence, like a counting sort.

To choose a more efficient sort - counting sort instead of comparison based sorting is the important decision in my practice, I read the question from another practice Leetcode 49 and bet that bottleneck is the string sorting issue.

My wishful thinking

So, I read through some of discussion of group of anagrams questions on this site, and then I like to emphasis this hash function design in my question, hopefully it brings the community some thoughts about hash function in algorithm problem solving.

Here is the C# code passing all test cases on Leetcode online judge. No time out issue. Please help me review.

using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode49_GroupAnagrams
{
  public class HashKeys
  {
    /* O(n) solution 
     * abc 
     * hashed to key:
     * 01-11-11
     * 0 stands for a, 1 is count of a
     * further simplify the key:
     * 1-1-1
     * first 1 is count of a, 
     * second 1 is count of b, 
     * third 1 is count of c
     * 
     * In the end, "abc" hashed key will be 
     * "1-1-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0"
     */
    public static string ConvertHashKeys(string input)
    {
        if (input == null || input.Length == 0)
        {
            return string.Empty;
        }

        int[] countAlphabetic = new int[26];

        foreach (char c in input)
        {
            countAlphabetic[c - 'a']++;
        }

        return String.Join("-", countAlphabetic);
    }
  }

  class Program
  {                
    /*
     * Leetcode 49 - group anagrams
     * https://leetcode.com/problems/anagrams/
     * 
     */
    static void Main(string[] args)
    {
        RunTestcaseHashfunction();
        RunSampleTestcase();             
    }

    public static void RunTestcaseHashfunction()
    {
        var key = HashKeys.ConvertHashKeys("abc");
        Debug.Assert(key.CompareTo("1-1-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0") == 0);

        // "xaba" and "xbaa" are anagrams, both are sorted 
        // to "aabx" in ascending order, but we prefer not to sort the string
        // because of time complexity concern. 
        var key2 = HashKeys.ConvertHashKeys("xaba");
        Debug.Assert(key2.CompareTo("2-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-1-0-0") == 0);

        var key3 = HashKeys.ConvertHashKeys("xbaa");
        Debug.Assert(key3.CompareTo("2-1-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-1-0-0") == 0);
    }

    public static void RunSampleTestcase()
    {
        string[] input = new string[]{"ape","and","cat"}; 

        GroupAnagrams(input);
    }

    public static IList<IList<string>> GroupAnagrams(string[] strs)
    {
        var groupAnagrams = new List<IList<string>>(); 

        var groupAnagramsWithKeys = new Dictionary<string, IList<string>>(); 

        foreach(string s in strs)
        {
            string key = HashKeys.ConvertHashKeys(s); 
            if(groupAnagramsWithKeys.ContainsKey(key))
            {
                var anagrams = groupAnagramsWithKeys[key]; 
                anagrams.Add(s); 
                groupAnagramsWithKeys[key] = anagrams; 
            }
            else{
                var anagrams = new List<string>(); 
                anagrams.Add(s); 
                groupAnagramsWithKeys.Add(key, anagrams); 
            }
        }

        foreach(var value in groupAnagramsWithKeys.Values)
        {
            groupAnagrams.Add(value); 
        }

        return groupAnagrams; 
    }
  }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Your whole description of a hash function is great, except what you have done is not a hashing function. If you really want to consider it a hashing function, because multiple words could end up with the same key, then that's a good thing because you've found an anagram. Your references to birthday attacks, and collisions, and "freedom of design" are all red-herrings. Those things are not really relevant to this problem at all. Focus.... and only communicate what's relevant. Otherwise people will move on when they can't deal with the "junk" that obscures the "meat" of the question. \$\endgroup\$ – rolfl Feb 5 '17 at 3:09
  • \$\begingroup\$ @rolfl, so good to read your statement. I am also training myself, when I worked on the algorithm myself, I was nervous and also confused, I finished around one hour, no timeout on leetcode online judge, I did not need to worry about 10,000 words test case: pastebin.com/x9jntRUW. O(n) hashing algorithm may avoid timeout instead of O(nlogn) sorting string to a key. So, I chose to bring up some hash function discussion and see if people will agree or not. We will see! \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 3:26
  • 1
    \$\begingroup\$ A hash function maps data of arbitrary size to data of fixed size. Your result is not fixed size so it's not a hash. \$\endgroup\$ – ChrisWue Feb 5 '17 at 18:38
  • \$\begingroup\$ @chrisWue, I also did study over one hour this morning. Here is the hash function I came cross from my study more than 12 months ago from hackerrank sherlock and anagram, one of submissions. gist.github.com/jianminchen/f75daa6055d7f0cb448b5248367551fc \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 18:42
  • \$\begingroup\$ @chrisWue, I have two concerns, 701 is a prime number, int value may be out-of-range if the string is a long one. I did not know Leetcode online judge how to design test cases. Will see how it works out. \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 18:44
3
\$\begingroup\$

Not really a hash

As rolfl pointed out in the comments, what you are generating isn't exactly a hash code. It's more like generating a unique key for each unique anagram. This key can then be used to insert/lookup in a hash set.

Choice of key

The obvious choice of key is just the sorted string. For example, "apple" would have a key of "aelpp". Your choice of key has advantages over sorted strings for large strings. If \$n\$ is the string length, the sorted string uses \$O(n)\$ space but your string uses \$O(\log n)\$ space. But your key uses a minimum of 51 bytes, so for small strings it is more inefficient.

Improvements on key format

One thing you could do is to omit counts for characters that do not appear in the string. To do this, you will need to use the characters themselves as delimiters instead of dashes. For example, "apple" would become "a1e1l1p2".

Another thing that you could do to improve upon the previous format is to omit the count of 1 for single characters. For example "aelp2". This key format is never longer than the original string, and is still logarithmic in space for long strings.

\$\endgroup\$
  • \$\begingroup\$ Not really a hash - I agreed with you. Here is one of approach using hash function, I will test it against Leetcode online judge. gist.github.com/jianminchen/f75daa6055d7f0cb448b5248367551fc \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 18:28
  • \$\begingroup\$ Choice of key - your space analysis is correct. The sorted string uses O(n) space but my string uses O(logn) space. I also felt that a minimum of 51 bytes key looks like silly, I am the designer, but it works based on simple reasoning. Not so tough as defining a hashing function, dealing with a prime number. \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 18:41
  • \$\begingroup\$ After careful review and comparison between using key with 52 bytes and using hashing function depending on string's maximum length, I chose this one as my answer. Thanks JS1 for great help. \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 22:15
0
\$\begingroup\$

This is the first time I answer one of my questions. Maybe I should make it a community wiki :-).

Hash function design

I did appreciate JS1 and all others help me to practice this algorithm. I did study one hour to go over hash function basic concepts after JS1's review, and reviewed one of the hash function's study I did after one of Hackerrank string problem - Sherlock and anagram in March 27, 2016.

I chose the same hash function as following:

public static string ConvertHashKeys(string s)
{
  if(s == null)
  {
    return string.Empty; 
  }

  var countAlphabetic = new int[26];
  for (int i = 0; i <= s.Length; i++)
  {
    countAlphabetic[s[i] - 'a']++;
  }

  int key = 0;                  
  for (int i = 0; i < 26; i++)
  {
    key = key * 701 + countAlphabetic[i];
  }

  return key.ToString();
}

I ran the submission again and it works for Leetcode online judge. I also questioned myself about hash function design last year, should I focus on the study of computer science or mathematics, cryptographic hash function? 701 is a prime number.

\$\endgroup\$
  • 1
    \$\begingroup\$ This hash and all other hashes have the problem that two different anagrams might hash to the same hash value. For example, in your hash, a string of 701 y characters and the string "z" would both hash to 701. \$\endgroup\$ – JS1 Feb 5 '17 at 19:12
  • \$\begingroup\$ @JS1, I did not agree with you on that. It is a polynomial hash function. f("z") = 1, but f("y") = 701. I am looking for a good article and then post here. \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 19:15
  • 1
    \$\begingroup\$ I wrote the wrong example. The hashes for "zzzzzzzzzzzzzzz...zzzzzzzzz" (701 z's) and "y" should both be 701. \$\endgroup\$ – JS1 Feb 5 '17 at 19:24
  • \$\begingroup\$ @JS1, you are correct on the calculation. I must have same question before more than 11 months ago. WE MAY MISS SOMETHING IMPORTANT! Certainly I can look into more if you can help me this time. \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 19:29
  • \$\begingroup\$ @JS1, I check the hackerrank sherlock and anagram problem statement, the string length is defined in the range of 2 to 100. Reference is here: hackerrank.com/challenges/sherlock-and-anagrams, so the Leetcode 49: group anagrams does not define the string's length, but test cases do not cover string's length more than 100, I checked the link 10000 word test case. Link is here:pastebin.com/x9jntRUW \$\endgroup\$ – Jianmin Chen Feb 5 '17 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.