Writing an anagram efficiently

Question

I know this question has been asked before now but in Python. Recently, I set out to write an anagram in C#. For instance, orchestra can be rearranged into carthorse and the anagram should not have more repeated than the original. The function is meant to check if the two words are the same and return true in this case. I started with putting the two words in two separate dictionaries with the letters as a key and the count as value.

The idea is using a dictionary ensures the keys can not be repeated. Then I looped through the second dictionary (secondString) and checked if each letter existed as a key in the first dictionary (firstString). Additionally, if the letter existed, the code checks if they have the same count. The rest of the code is self-explanatory.

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character)== true)
            {
                firstString[character]+=1;
            }
            else
                firstString[character]=1;
        }
        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2)== true)
            {
                secondString[character2]+=1;
            }
            else
                secondString[character2]=1;
        }

        foreach(KeyValuePair<char,int> letterValue in secondString)
        {
            if(firstString.ContainsKey(letterValue.Key))
            {
                if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        //throw new NotImplementedException("Waiting to be implemented.");
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

But I scored 75% and I feel this can be improved on. Also, is there any easy conversion from string to dictionary?

Answer 1

I took your new code and cleaned it up a bit by

• adjusting bracket location
• removed unnecessary nesting of if statements
• gave some operations some breathing room
• fixed some odd indentations

I took your code

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
      Dictionary<char,int> firstString = new Dictionary<char,int>();
      Dictionary<char,int> secondString = new Dictionary<char,int>();

      foreach(char character in a)
      {
          if(firstString.ContainsKey(character))
          {
              firstString[character]+=1;
          }
          else{
              firstString[character]=1;
              }
      }

      foreach(char character2 in b)
      {
          if(secondString.ContainsKey(character2))
          {
              secondString[character2]+=1;
          }
          else{
              secondString[character2]=1;
              }
      }


      if(firstString.Count !=secondString.Count){
          return false;
      }
      else   {
              foreach(KeyValuePair<char,int> letterValue in secondString)
                  {
                      if(firstString.ContainsKey(letterValue.Key))
                      {
                          if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                              return false;
                              }
                      }
                      else
                      {
                          return false;
                      }
                  }
              }
      return  true;
  }

  public static void Main(string[] args)
  {
      Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
  }
}

and refactored it to this (there is an issue with the if then statement inside last for loop, which I address later)

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character))
            {
                firstString[character] += 1;
            }
            else
            {
                firstString[character] = 1;
            }
        }

        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2))
            {
                secondString[character2] += 1;
            }
            else
            {
                secondString[character2] = 1;
            }
        }

        if(firstString.Count != secondString.Count)
        {
            return false;
        }
        else   
        {
            foreach(KeyValuePair<char,int> letterValue in secondString)
            {
                if(firstString.ContainsKey(letterValue.Key) 
                    && (firstString[letterValue.Key] != secondString[letterValue.Key]))
                {
                    return false;
                }
                else
                {
                    return false;
                }
            }
        }
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

---

I also decided to change this so that there are two separate if statements, this will reduce the O(n) in the optimistic case (Your code cleaned up)

foreach(KeyValuePair<char,int> letterValue in secondString)
{
    if(firstString.ContainsKey(letterValue.Key))
    {
        if(firstString[letterValue.Key] != secondString[letterValue.Key]){
            return false;
        }
    }
    else
    {
        return false;
    }
}

New Code with less complexity

foreach(KeyValuePair<char,int> letterValue in secondString)
{
    if (!firstString.ContainsKey(letterValue.Key))
    {
        return false;
    }
    if (firstString[letterValue.Key] != secondString[letterValue.Key])
    {
        return false;
    }
}

You could merge these into a single if statement, but for the sake of reading I left them separate here.

If one doesn't contain the key of the other one, you want to return false, no need to check the other condition.

---

Another overall thing that you could do to reduce the O(n) is to evaluate if the strings are the same length, immediately and return false if they are not, because you already know they cannot be anagrams of each other.

like this

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        if (a.Length != b.Length) {
            return false;
        }

        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

       /// ...

then you can remove the check later in the code.

I did that, and also changed += 1 to ++ twice in your code. I also made it case insensitive, but sentences will not work.

Here is the code that works, I tested with your example and with Joker and JReko

if (a.Length != b.Length)
{
    return false;
}

Dictionary<char, int> firstString = new Dictionary<char, int>();
Dictionary<char, int> secondString = new Dictionary<char, int>();

foreach (char character in a.ToLower())
{
    if (firstString.ContainsKey(character))
    {
        firstString[character]++;
    }
    else
    {
        firstString[character] = 1;
    }
}

foreach (char character2 in b.ToLower())
{
    if (secondString.ContainsKey(character2))
    {
        secondString[character2]++;
    }
    else
    {
        secondString[character2] = 1;
    }
}

foreach (KeyValuePair<char, int> letterValue in secondString)
{
    if (!firstString.ContainsKey(letterValue.Key)
        || (firstString[letterValue.Key] != secondString[letterValue.Key]))
    {
        return false;
    }
}

return true;

Answer 2

There seems to be a lot of answers but not much explaining why one would be better than the others. Generally when improving on a solution, you either want to cut down on memory usage or execution time. Memory usage is pretty easy to track and in Computer Science we have Big-O notation to figure out worst case execution time.

I'll preface this with I'm doing this all in my head so I maybe off here and there.

So lets take the final code that Malachi provided and first go through worst case execution time.

1. Populating firstString dictionary - O(n)
2. Populating secondString dictionary - O(n)
3. Then we iterate over the second dictionary - O(n)
4. Do a look up in the dictionary - O(1) And finally return

So execution wise this is O(3n) which would just simplify down to O(n)

Memory wise we are creating a lot of pointers here. Each dictionary is a pointer, the pointer to the key and the pointer to the value are all either 32bit or 64bit depending on your .Net system. Then the iteration of the KeyValuePair creates yet another pointer along with some underlying logic to create the class that holds those values (I'm too lazy to go look up the open source code).

Overall we have

• 1 pointer for each dictionary
• n pointers for each character in the key
• n pointers for the values
• n char (which is an int)
• n int And all that multiplied by 2 since we have two of them

So on a 64 bit machine where pointers are 8 bytes and ints are 4 bytes this ends up being 2 * (8 + 8*n + 8*n + 4*n + 4*n) and this doesn't even include the creation of the KeyValuePair stuff.

Now lets take a look at something that maybe a bit less execution efficient but likely more memory efficient.

public static bool AreStringsAnagrams(string a, string b)
{
    if (a == b)
    {
        return true;
    }
    if (a == null || b == null)
    {
        return false;
    }
    if (a.Length != b.Length)
    {
        return false;
    }

    var charInA = a.ToCharArray();
    var charInB = b.ToCharArray();

    Array.Sort(charInA);
    Array.Sort(charInB);

    for (int i = 0; i < charInA.Length; i++)
    {
        if (charInA[i] != charInB[i])
        {
            return false;
        }
    }

    return true;
}
static void Main(string[] args)
{
    Console.Out.WriteLine(AreStringsAnagrams("orchestra", "carthorse"));
    Console.ReadKey();
}

So worst case run time here would be:

1. Copy all characters in string a to array - O(n)
2. Copy all characters in string b to array - O(n)
3. Sort charInA - O(nlog(n))
4. Sort charInb - O(nlog(n))
5. Iterate through both sorted arrays and see if there are any differences - O(n)

Memory would be the following:

1. Copy all characters in string a to array - n * 4 bytes
2. Copy all characters in string b to array - n * 4 bytes Total 8 * n bytes.

So it all depends on what you want to optimize here memory or time.

And there are ways of combining both solutions, for example:

public static bool AreStringsAnagrams(string a, string b)
{
    if (a == b)
    {
        return true;
    }
    if (a == null || b == null)
    {
        return false;
    }
    if (a.Length != b.Length)
    {
        return false;
    }

    Dictionary<char, int> firstString = new Dictionary<char, int>();
    foreach (char character in a)
    {
        if (firstString.ContainsKey(character))
        {
            firstString[character]++;
        }
        else
        {
            firstString[character] = 1;
        }
    }

    for (int i = 0; i < b.Length; i++)
    {
        if (!firstString.ContainsKey(b[i]))
        {
            return false;
        }
        else
        {
            firstString[b[i]]--;
        }

        if (firstString[b[i]] < 0)
        {
            return false;
        }
    }

    return true;
}

which reduces the number of dictionaries to 1 but still maintains an O(n) worst case runtime.

Data collections are useful but tend to be memory intensive if used incorrectly. Just something to keep in mind :-).

Also broader community, it's pretty easy to see when someone is posting a homework assignment. I'm posting this larger analysis because the poster said they already got a 100%. Is there a policy regarding doing other peoples homework questions on this site? Seems like we should guide people to the answer in that situation, not give them the answer... or else I wouldn't have learned anything in university!

Answer 3

It looks like you got your answer for making it more efficient. Here is how you can use LINQ to make your code (in my opinion) more concise, safer, and more readable.

To create a dictionary with the count of each letter, you can group a collection of letters by their value, get each group's count, and then convert the result into a dictionary:

Dictionary<char,int> firstString = a.GroupBy(x => x).ToDictionary(g => g.Key, g => g.Count());

The body of the foreach loop that helps determine if the strings are anagrams can be condensed into one if statement:

if(!firstString.ContainsKey(letterValue.Key) ||
   firstString[letterValue.Key] != secondString[letterValue.Key])
{
    return false;
}

You can actually replace that foreach loop and the if statement above it with code similar to this answer to determine if two dictionaries are equal:

return firstString.Count == secondString.Count && !firstString.Except(secondString).Any();

Edit: You can check if the strings are the same length right away to avoid doing extra work when they aren't. Thanks to JonathanR for the suggestion.

The class then looks like this:

using System;
using System.Collections.Generic;
using System.Linq;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        if(a.Count() != b.Count())
        {
            return false;
        }
        Dictionary<char,int> firstString = a
            .GroupBy(x => x)
            .ToDictionary(g => g.Key, g => g.Count());
        Dictionary<char,int> secondString = b
            .GroupBy(x => x)
            .ToDictionary(g => g.Key, g => g.Count());
        return firstString.Count == secondString.Count &&
               !firstString.Except(secondString).Any();
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

If you want, you can extract the code that converts a string to a dictionary into a method, since it's used twice. Because the string lengths are checked right away, firstString.Count == secondString.Count && is not necessary if you want to leave that out.

Edit 2: k2snowman69 pointed out that you could sacrifice some speed for less memory usage by avoiding dictionaries and instead sorting both strings and comparing each character in sequence. Now I have an excuse to post this solution, which not only does that, but is shorter and a lot more readable:

public static bool AreStringsAnagrams(string a, string b)
{
    return a.Count() == b.Count() && a.OrderBy(x => x).SequenceEqual(b.OrderBy(x => x));
}

Answer 4

How about this:

bool AreAnagrams(string a, string b)
{
    return Enumerable.SequenceEqual(
        a.Normalize(NormalizationForm.FormC).OrderBy(c => c),
        b.Normalize(NormalizationForm.FormC).OrderBy(c => c));
}

Shorter and very readable. First it normalizes the string, which solves the issue raised in RobH's answer. Then it arranges the characters of each string into alphabetical order, which should return the same sequence for both strings if they are anagrams. Finally it compares those two sequences.

Your original attempt, and a lot of these answers, seem to involve a hell of a lot of code. I would suggest that unless you're looking for micro-optimised performance, this is a good implementation.

Answer 5

After adding a little detail based on Jonathan's help. The full code is

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char,int> firstString = new Dictionary<char,int>();
        Dictionary<char,int> secondString = new Dictionary<char,int>();

        foreach(char character in a)
        {
            if(firstString.ContainsKey(character))
            {
                firstString[character]+=1;
            }
            else{
                firstString[character]=1;
                }
        }

        foreach(char character2 in b)
        {
            if(secondString.ContainsKey(character2))
            {
                secondString[character2]+=1;
            }
            else{
                secondString[character2]=1;
                }
        }


        if(firstString.Count !=secondString.Count){
            return false;
        }
        else   {
                foreach(KeyValuePair<char,int> letterValue in secondString)
                    {
                        if(firstString.ContainsKey(letterValue.Key))
                        {
                            if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                                return false;
                                }
                        }
                        else
                        {
                            return false;
                        }
                    }
                }
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

Answer 6

An example of the sort of structural change Risky Martin suggested.

If you want, you can extract the code that converts a string to a dictionary into a method, since it's used twice.

Your lines 11-19:

foreach(char character in a)
{
    if(firstString.ContainsKey(character)== true)
    {
        firstString[character]+=1;
    }
    else
        firstString[character]=1;
}

lines 20-28:

foreach(char character2 in b)
{
    if(secondString.ContainsKey(character2)== true)
    {
        secondString[character2]+=1;
    }
    else
        secondString[character2]=1;
}

See how similar these are? A pretty sound principle is to not have repeat blocks of code like this. Instead you can take all the only-slightly-differing parts of code (watch for variables with similar names), make them generic, add some declarations and put the block into a new function. Then you get:

public static Dictionary<char, int> newFunction(string z)
{
    Dictionary<char, int> z = new Dictionary<char, int>();
    foreach(char y in x)
    {
        if(z.ContainsKey(y)== true)
        {
            z[y]+=1;
        }
        else
            z[y]=1;
    }
    return z;
}

I'd advise (for readability) against leaving such generic variable names in place, and you should pick a meaningful function name (I originally was going to use "countChars()" but that sorta sounded like it was just going to count the total number of characters - find your own balance between ambiguous names and overly specific/long names). So I'd actually render this as:

public static Dictionary<char, int> tallyByDistinctChar(string characters)
{
    Dictionary<char, int> numChars = new Dictionary<char, int>();
    foreach (char c in characters)
    {
        if (numChars.ContainsKey(c))
            numChars[c] += 1;
        else
            numChars[c] = 1;
    }
    return numChars;
}

Or I might condense it by using a ternary (the " ? : " construct) because it easily fits on one line:

public static Dictionary<char, int> tallyByDistinctChar(string characters)
{
    Dictionary<char, int> numChars = new Dictionary<char, int>();
    foreach (char c in characters)
        numChars[c] = numChars.ContainsKey(c) ? (numChars[c] + 1) : 1;

    return numChars;
}

Which turns the whole code into:

using System;
using System.Collections.Generic;

public class AreAnagrams
{
    public static Dictionary<char, int> tallyByDistinctChar(string characters)
    {
        Dictionary<char, int> numChars = new Dictionary<char, int>();
        foreach (char c in characters)
            numChars[c] = numChars.ContainsKey(c) ? (numChars[c] + 1) : 1;

        return numChars;
    }

    public static bool AreStringsAnagrams(string a, string b)
    {
        Dictionary<char, int> firstString = tallyByDistinctChar(a);
        Dictionary<char, int> secondString = tallyByDistinctChar(b);

        foreach(KeyValuePair<char,int> letterValue in secondString)
        {
            if(firstString.ContainsKey(letterValue.Key))
            {
                if(firstString[letterValue.Key] != secondString[letterValue.Key]){

                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        //throw new NotImplementedException("Waiting to be implemented.");
        return  true;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));
    }
}

Then I'd the alter the style of lines 20-35 (and add the length check shortcut) but I've left the rest of your code as is for clarity/contrast.

Something else to think about: Do you want to consider a string to be it's own anagram?

Answer 7

Without changing the heart of your program, I refactored/rewrote it down to this

public static bool AreStringsAnagrams(string a, string b)
{
    var firstString = a.GroupBy(val => val).ToDictionary(letter => letter.Key, letter => letter.Count());
    var secondString = b.GroupBy(val => val).ToDictionary(letter => letter.Key, letter => letter.Count());


    foreach (var kvp in firstString)
        if (!secondString.ContainsKey(kvp.Key) || secondString[kvp.Key] != kvp.Value)
            return false;

    return firstString.Keys.Count == secondString.Keys.Count;
}

In your original program, you had some inconsistencies with your usage of brackets, and there were places where you could have condensed your if-statements into single statements. I'm more interested in seeing you learn the power of LinQ.

First two lines are spent creating a dictionary exactly the same as you were before, except using LinQ to do so. First step is taking the list of letters you have (string) and grouping them by their value a.GroupBy(val => val). This returns a collection of IGrouping objects. On this collection, we then call ToDictionary(KeySelector, ValueSelector). For the key I specify, that I want the grouped value letter => letter.Key which is simply the letter its self. For the value, we want how many times that letter was in the original string, which is just the count of that letter in the grouping letter => letter.Count(). Keep in mind in both of these selectors, that the letter value is the IGrouping object.

After that I run through the firstString, and check to make sure that every key that is in the first dictionary, is also in the second dictionary. When I confirm that, I ensure that their values (counts) are the same. If at some point, this is not true, I simply return false at that moment.

After all that, we know the first string is at-least contained in the second one, but we don't know if the second string perhaps has additional other characters. If we just returned true right now, it is possible that a = "hi", b = "hiaaaaa" would return true. So all we have to do, is make sure that they key count is the same, that way we know there are no more other letters, and we know we've already verified that the counts of the ones that do exist in the first string are valid, so just a key count comparison is all we need.

---

If you were looking reduce the amount of code further, you could probably skip the whole dictionary part of this, and just compare the lists returned from the GroupBy, by intersecting them and subtracting one list from the other.

I just had to try :)

public static bool AreStringsAnagrams(string a, string b)
{
    return     a.GroupBy(val => val).Select(letter => new { Letter = letter.Key, Count = letter.Count() })
        .Union(b.GroupBy(val => val).Select(letter => new { Letter = letter.Key, Count = 0 - letter.Count() }))
        .GroupBy(letters => letters.Letter)
        .Where(letters => letters.Sum(letter => letter.Count) != 0)
        .Count() == 0;
}

In this alternate solution, you'll notice that I use LinQ to Union the two lists. For the second list, you may also see that I set the count to be negative, so when I re-grouped them again and did a sum of their Count values, they would subtract from each other. Then after that I do a Where checking for anything that wasn't zero'd out by the subtraction. Then return whether or not the collection contains any of those.

Answer 8

Most of these suggestions are style-based, but I think they can be helpful to you either way.

Code Consistency

Your if-statements have a mix of inconsistencies.

1. Always use brackets. Even if the statement afterward is a one-liner just use them, it'll prevent a rookie mistake in the future. Secondly, if you insist on not using brackets, be consistent. You have an if-statement with brackets and the else-statement doesn't.
2. Curley bracket placement. The standard for C# is placing brackets on their own line. You have spots where you do this, but you also have spots where you place the opening curley bracket on the same line as the if-statement.

Efficiency

1. As JonathanR suggested, check if their lengths match, if not then there is no point in doing all that other work.

Answer 9

A Bug!

It's always fun to point out edge cases when everyone starts thinking that you can reliably process a string as an array of characters. I'll chose a simple one - I'll pass the same word as both strings and show that all of the answers on this page return the incorrect answer.

What's my test case? café

E-acute is an amazing letter - it can be represented as a single char in .Net ((char)233) == 'é' but it can also be two char instances: 'e' and '\x0301' (e and the combining acute accent character).

Armed with that knowledge - let's plug it in:

var cafe1 = "café";
var cafe2 = "cafe\x0301";
Console.WriteLine(cafe1);
Console.WriteLine(cafe2);
Console.WriteLine(AreStringsAnagrams(cafe1, cafe2));

That will print:

café
café
False

Are these kinds of edge cases important? Probably not if you're only interested in input that you control that you know isn't trying to deliberately trip you up (unlike me). It is worth knowing that they exist though!

Answer 10

First, check if the strings are the same length, if not return false.