What are anagrams?

An anagram is the rearranging of letters of a word to make other words with meaning. The word itself is an example because you can rearrange the letters to spell words with one less character. The word Anagram can be rearranged into ragman or Amarna as an example but there is a missing letter. When researching this topic, I was surprised to learn how rich the history of this was and I learned that it dates back to the ancient Greeks and Romans. [1], [2].

How is this relevant to my life?

If you are a developer you may have run into this type of interview question already. I have seen interviewers ask this one right after the palindrome question. If you are new to this field it can be intimidating if you have not prepared for a code interview like the ones I am referring to. It is important to know how to explain what this is, how to implement it on the white board and in a virtual coding interview. Other than what I described above this is a nice to know in case the panel decides to throw it at you during the interview process.

Complexity Analysis

As simple as an anagram seems, we can actually analyze how long an iterative algorithm implementation would run. If you had N characters from two words you can complete it in the worst case in O(2N) by ordering the characters of each word and then comparing.

Real Examples

As I was preparing for this article I found it interesting how many ways a developer could implement an algorithm to determine if two words are anagrams of each other or finding all the possible combinations for one word. The following are just a few of the ones I either figured out on my own or adapted from various sources.

First example in C# – Determine if two words are anagrams of each other for the same count as both words.

bool isAnagram = false;
var word1 = "dog";
var word2 = "god";

isAnagram = input1.OrderBy(x => x).SequenceEqual(input2.OrderBy(x => x));

Interface implementation variation 1

This determines if two words of the same count or different count are anagrams.

public bool IsAnagram(string input1, string input2)
        {
            if(input1 == null)
                return false;

            if (input2 == null)
                return false;

            var ordered1 = input1?.OrderBy(c => c);
            var ordered2 = input2?.OrderBy(c => c);

            if (ordered1 == null)
                return false;

            if (ordered2 == null)
                return false;

            bool? isEqual = false;
            if (input1?.Length == input2?.Length)
            {
                isEqual = ordered1?.SequenceEqual(ordered2.AsEnumerable());
                return System.Convert.ToBoolean(isEqual);
            }
            else
            {
                //in this case the input2 is a subset of the letters in input1.
                if(input1?.Length > input2?.Length)
                {
                    ordered2?.ToList().ForEach(c =>
                    {
                        isEqual = ordered1.Any(x => x.Equals(c));
                    });
                }
                else
                {
                    //vice versa, input1 is a subset of input2
                    ordered1?.ToList().ForEach(c =>
                    {
                        isEqual = ordered2.Any(x => x.Equals(c));
                    });
                }
            }

            return System.Convert.ToBoolean(isEqual);
        }

References

[1] Anonymous, “Anagrams” retrieved from https://www.yourdictionary.com/anagram

Accessed 4 July 2023

[2] Anonymous, “Palindromes” retrieved from https://www.yourdictionary.com/palindrome

Accessed 4 July 2023

[2] Britannica, The Editors of Encyclopedia. “Anagram”. Encyclopedia Britannica, 23 Apr. 2020, https://www.britannica.com/topic/anagram. Accessed 1 September 2021.