Pairing anagrams in a string list

Question

The task was to check for pairs of anagrams in a string list.

1. I first sorted all the words. and looped over the letters.
2. The interview continues with a follow-up, to do the same with limited memory. I tried to implement a Hash function.

The dictionary return value is only for my convince in order to see all the pairs. I could just print it into the console instead.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Security.Cryptography;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApplication2
    {
    public class ReverseString
    {
        public ReverseString()
        {                 
            List<string> anagarms = new List<string>();
            anagarms.Add("Gilad");
            anagarms.Add("dilaG");
            anagarms.Add("bat");
            anagarms.Add("but");
            anagarms.Add("utb");
            pairs = PairAnagrams(anagarms);
            pairs = PairAnagramsHash(anagarms);
        }

        Dictionary<string, string> PairAnagrams(List<string> wordsList)
        {
            Dictionary<string, string> dictionary = new Dictionary<string, string>();
            foreach(var item in wordsList)
            {
                if (dictionary.ContainsValue(item))
                {
                    continue;
                }
                foreach(var item2 in wordsList)
                {
                    if(item.Length != item2.Length || item.Equals(item2))
                    {
                        continue;
                    }

                    var sortedWord1 = item.ToArray();
                    Array.Sort(sortedWord1);
                    var sortedWord2 = item2.ToArray();
                    Array.Sort<char>(sortedWord2);
                    int i;
                    for (i = 0; i < sortedWord2.Length; i++)
                    {
                        if (sortedWord2[i] != sortedWord1[i])
                        {
                            break;
                        }
                    }
                    if(i == sortedWord1.Length)
                    {
                        dictionary.Add(item, item2);
                    }
                }
            }
            return dictionary;
        }

        Dictionary<string, string> PairAnagramsHash(List<string> wordList)
        {
            Dictionary<string, string> dictionary = new Dictionary<string, string>();

            foreach (var item in wordList)
            {
                foreach (var item2 in wordList)
                {
                    if (item.Equals(item2) || dictionary.ContainsKey(item2))
                    {
                        continue;
                    }
                    if (HashFunction(item) == HashFunction(item2))
                    {
                        dictionary.Add(item, item2);
                    }
                }
            }
            return dictionary;
        }

        public int HashFunction(string word)
        {
              int result = 0;
              var charArray = word.ToArray();
              for (int i = 0; i < word.Length; i++)
              {
                  result += charArray[i] * 37;
              }
              return result;
        }
    }
}

Answer 1

Algorithm of PairAnagrams()

You are calling

var sortedWord1 = item.ToArray();
Array.Sort(sortedWord1);

inside the inner loop, but item won't change there.

One time you are using Array.Sort(sortedWord1); and two lines below Array.Sort<char>(sortedWord2); Be consistent in your style.

This

for (i = 0; i < sortedWord2.Length; i++)
{
    if (sortedWord2[i] != sortedWord1[i])
    {
        break;
    }
}
if (i == sortedWord1.Length)
{
    dictionary.Add(item, item2);
}  

can be replaced by

if (sortedWord1.SequenceEqual(sortedWord2))
{
    dictionary.Add(item, item2);
}  

By using .Where() on the wordList at the for each you can omit the check for length and equal.

By using the .OrderBy() on the chars of the words, there won't be a need to call .ToArray() and Array.Sort().

This reduces the code to

Dictionary<string, string> PairAnagrams(List<string> words)
{
    Dictionary<string, string> pairedAnagrams = new Dictionary<string, string>();
    foreach (var word in words)
    {
        if (pairedAnagrams.ContainsValue(word))
        {
            continue;
        }

        var sortedWord1 = word.OrderBy(c => c);
        int wordLength = word.Length;
        foreach (var word2 in words.Where(w => w.Length == wordLength && !word.Equals(w)))
        {
            if (sortedWord1.SequenceEqual(word2.OrderBy(c => c)))
            {
                pairedAnagrams.Add(word, word2);
            }
        }
    }
    return pairedAnagrams;
}

Constructor

The constructor of an object should be used only for constructing the object. You are misusing it to start the action.

Naming

• variable names should be correctly spelled. anagarms vs anagrams
• parameters should't be pre/post fixed by their types. List<string> wordsList-> List<string> words

General

• no need for using System.Security.Cryptography

Answer 2

Challenged by a friend, I did this in C the other day. My hash-code proceeded as follows for a string S[i] where i ranges 1 to n.

1. Assign each letter of the alphabet to an odd prime P(Letter).(P(A)=3,P(B)=5,P(C)=7...)
2. Set H=0
3. For each letter S[i] in the string S
4. Calculate T=(P(S[i])-1)/2
5. Calculate H=2*H*T+H+T
6. End Loop
7. Return H as Hash-code.

This has the nice property that is invariant for the order of letters (essential for anagrams!) and by the Fundamental Theorem of Arithmetic is collision low. Notice the hash-code is H such that 2*H+1 is the product P(S[1])P(S[2])...*P(S[n]). Without that transform the hashcode is 100% biased in the lowest bit. If we use 2 as one of the primes it tends to degrade the hash-code if K such that P(K)=2 occur frequently in the string being hashed.

In terms of performance it can find all the anagram pairs in a 179,000 input table of English words in just over a 1s on a mid-range laptop with a hash-table with only 20K buckets.

That word list was a 179,000 word plain-text English dictionary.

It found no 32-bit collisions. That is where H is 32-bits no two words were found where H(W1)=H(W2).

If it helps I'll dig it out and put it up for review.

Performance is theoretically improved by assigning low primes to the most frequent letters. But given you can't get fewer than zero full-length collisions it hardly seems worth the worry.